Yo tampoco entiendo.
Si no te ayuda tu proveedor, que es supuestamente un VPS "manejado" o si por lo menos no te ayudan a identificar claramente el problema, la solución caería en alguna de estas 3 opciones:
1. Aprendes cómo administrar un equipo Linux, cómo identificar cuellos de botella y cómo optimizar Apache y MySQL para el entorno específico de hardware en el que te encuentras y para el uso específico del mismo.
2. Contratas a una empresa que administre el VPS por tí.
3. Contratas con un "buen" proveedor, uno realmente manejado.
Saludos.