Si no lo tienes ya, prueba a crear un índice por el/los campos que estés haciendo el Order By.
De todas maneras, si tus usuarios se desesperan por una demora de 4-6 sg....
PD: también todo depende del volumen de información que estés moviendo, mira de acotar bien con el Where