Is it every page in admin, or just certain pages? Have you tried turning on page parse times? Have you tried turning on the slow query log in MySQL? Have you tried manually deleting old values from the session table? Some servers don't do that automatically. There's code floating around to do it by hook.
If the page parse time is low but the page speed is high, it may be something happening at the Apache (web server) level. For example, htpasswd strength too high:
https://stackoverflow.com/a/64722818/6660678
For more help with that, post the algorithm from the admin/.htpasswd_phoenix file.
User1:$apr1$salt$passwordhash
User2:$2y$10$passwordhash
The algorithms are $apr1$ and $2y$10$ in those examples. Do not post the user names or password hashes in the forum. The salts would probably be all right but are not needed anyway. $2y$10$ to $2y$12$ should not be terribly slow on a maxed out VPS.
You'd probably have to be on 1.0.8.2 or newer to change the algorithm. But again, a maxed out VPS should not have trouble with apr1.
Large numbers of orders/customers should only impact pages that work with orders/customers. And even on those pages, I wouldn't expect a hundred thousand to significantly slow most queries. That's a big number for the kind of independent stores that run Phoenix. (Congratulations!) But it's not really a big number to a database.
If you can identify particular slow queries, we could likely provide more help with optimizing those.
Depending on your current version, you might find a newer version to be faster. For example, Burt observed a 20% speed improvement from 1.0.7.0 to 1.0.7.2 in catalog on one of his sites.
For speeding up a particular page, consider the following pieces of data:
1. Which page?
2. What action on the page? E.g. the default view, edit, preview, what?
3. The default version of that page action, or are you restricting by something? E.g. on the orders page, you might restrict the default list view by customer or order status.
4. Do you get a long list of results or just one or two?