O problema pode ser que esses servidores estão tentando autenticar sua máquina cliente de uma forma que é opcional (para que você possa eventualmente efetuar login), mas onde descobrir onde o método está disponível expira.
Um caso comum é quando o servidor tenta uma pesquisa de DNS reversa no cliente. Tente desativá-lo no HOST: adicione UseDNS No
ao arquivo sshd_config
. Esta opção está ativada por padrão, mas é basicamente inútil. Pode levar a tempos limite, mas geralmente apenas alguns segundos. Veja Qual é o sentido da opção “UseDNS” do sshd?
Outro culpado menos comum mas mais chato é o GSSAPI (Kerberos). Mais uma vez, tente desligá-lo. Veja Como acelerar meu login ssh muito lento?