Reduce latency in loading a page in Drupal 6
The database query time is just the database interaction, don't forget that PHP takes time to process its own logic.

If the majority of the page load time is outside the database you should install xhprof to actually profile your PHP functions individually to see where the damage is being done.

Basic tips for improving PHP performance - install a module like Cache Router to take caching out of the database and put it somewhere else like in memory or the file system.

Install APC or similar on your server to improve PHP performance.

Cache object load calls wherever possible, this is handled much more easily in D7 thanks to the Entity Cache module, but it is possible to do in D6. Persistent caching of node_load() can really be your friend.

Avoid configuring your site to load a lot of tpl.php files on page loads - "fields" rendering mode in Views can do this.

Avoid "slow" core functions - some taxonomy functions can be very slow in D6, be aware that user_load() is not even statically cached so it can be expensive if you call it a lot.

Avoid eval()'d code as it runs much slower as well as being a potential security risk - This is anything using the PHP input filter.

Disable all "UI" modules. If you're running a large number of modules it is very easy for one of them to be doing more than it "should" be, so you want to start whittling the total number down if possible. Unfortunately, modules smart enough to split their logic into "core" and "UI" often aren't the culprits for performance problems but it's worth doing anyway since it is so easy to do.

If it isn't PHP or the database that is slowing things down, your server could be under too much load and doesn't have the processing power to keep up with incoming requests. If you can process X number of requests per second and have 2*X incoming requests then your pages will load about 1/2 as fast.

Make sure you have enough RAM to run your site comfortably, if your server starts "swapping" things can degrade very quickly.

Page Caching does not help at all for authenticated traffic, only anonymous traffic. Make sure that your block caching settings are correct for every custom block that you've created. It might be worth trying the auth cache module.

Unfortunately there are many, many ways to slow a site down so these tips are not really comprehensive. I used to have a bookmark to "56 tips" that you could basically review your site with and at least triple the speed but it was pulled offline at some point in the past couple of years :(

Also, you might want to try swapping to innoDB as the row-level locking can speed things up drastically over myISAM in some cases.