Primeiro, para coletar mais informações sobre o atraso, tente se conectar com o detalhamento ativado: ssh -vvv user@hostname .
Segundo, tente desabilitar a pesquisa inversa de DNS - edite /etc/ssh/sshd_config no seu dispositivo e configure UseDNS no . Reinicie o serviço e verifique novamente.
Terceiro, configure GSSAPIAuthentication no no mesmo arquivo, reinicie o serviço e tente novamente.
Aqui você pode ver um bom exemplo, eu usei no passado.