En el servidor compartido no notabas que fuese mas lento por que tenias mas recursos para utilizar que en el VPS
Servidor compartido = 4gb de ram minimo y un Dual Core 2.4gh
VPS = Virtual Private Server = 128-512mb ram y aprox ~1gh de cpu
Supongo que te pasastes a un VPS x que tu hosting asi te lo indico, esto es la politica normal en muchas empresas de hosting, venden a los clientes el plan mas barato, cuando el cliente entra a utilizar recursos del Servidor compartido como por ejemplo ciclos de cpu o ram por encima de un X te invitan a pasarte a un VPS pero no te explican que el VPS tiene X limitante de cpu y ram los cuales no puedes pasar como antes si hacias. [ademas de que muchos hacen overselling con los vps tambien, es decir que venden 300 vps de 1ghz y 512 de ram en un servidor Quadcore con 8gb de ram, eso hace que si todos usan los recursos que se le asignan no alcance para todos]
Que quiere decir toda esta pedorata. que tu servidor queda "de rodillas" (anda todo lento) por que el mysql esta hasta "tragandose todos los recursos del mismo" (utilizando todos los ciclos del cpu que te dieron)
Soluciones:
1 - analizar, reparar y optimizar todas tus bases de datos/tablas mysql desde phpmyadmin
2 - limpiar tu/tus bases de datos (no deberias tener nunca DB de mas de 1gb en un VPS)
3 - optimizar la instalacion del mysql (conex concurrentes, persistencia, etc)
4 - optimizar la aplicacion web que usa mysql para hacer menos querys a la base de datos, cerrar conexiones y muchas cosas mas que muchas aplicaciones PHP hacen espantosamente mal
5 - implementar un sistema de cache en tu aplicacion web
6 - cambiar de VPS o a un server dedicado. A esta opcion solo deberias llegar si tienes mucho dinero y no te importa gastarlo o tienes mucho mucho trafico y por mas optimizacion y cambios que hagas sigues con el server de rodillas.
/espero que te sea util la info
:wq