Você ainda não excluiu o DNS, porque nslookup não é o mesmo que nginx ou PHP executando a requisição. Veja os pedidos de DNS para ver se algum deles é patentemente bobo.
Sempre que algo é inesperadamente lento (solicitação HTTP, conexão ssh inicial, etc), mas apenas lento no começo , geralmente é uma solicitação reversa de DNS que está expirando.