Eu também verifico seu DNS ... talvez. O servidor que você está conectando pode resolver o DNS corretamente? Você poderia adicionar uma entrada de host temporária com seu IP de origem no servidor para testar?
Veja: SSH leva cerca de 30 segundos para conectar no meu computador