mmm .. creo que habría que ver primero realmente el tiempo de proceso de tu script PHP (incluido los accesos a tus BD si los hay) .. para eso puedes ver una de las últimas FAQ's que hay (lo siento no tengo el link a mano) que se basa en el uso de microtime() (
www.php.net/microtime) para averigüar cual (realmente) es el tiempo de proceso de PHP .. Así vamos descartanto problemas de "lógica" PHP que puedan afectar al rendimiento o bien temas del lado del "cliente" (por ejemplo si usas algo de javascript .. o tu página en si .. etc .. ) y/o de la conexión en sí (no comentas si haces pruebas locales o como.
Un saludo,