Parece que suas conexões com o banco de dados estão lentas devido a algum outro motivo. Quão rápido é uma conexão de linha de comando simples? (isto é, não-php)
Meu principal suspeito seria falhar (= tempo limite) pesquisas de DNS no servidor remoto ou local; pesquisa direta e inversa.
De esta página : inicie o mysqld com - skip-name -resolve
Se isso não ajudar, eu começaria a analisar as conexões tcp (tcpdump / wireshark) para isolar o problema. (no topo da minha cabeça: pesquisas de DNS locais, problemas de firewall (caixa NAT sobrecarregada em algum lugar?), perda de pacotes no link em algum lugar, ..)
Quando este problema for resolvido, você provavelmente também desejará ter certeza de ter conexões permanentes de banco de dados no PHP.