My users have had similar complaints in the last few months. I checked and it seems to be mysqld which is choking. We have a relatively small forum too.
I'm not sure if this helps or not, but it seems to be worse on the main forum page. by clicking on "Forum List", here is an example of the slowness in debug info:
Generated in 24.950 seconds in which 24.585 seconds were spent on a total of 23 queries. Zlib compression enabled.
