En un caso muy similar, fue uno de los scripts update-motd.
Lo siguiente hizo el truco:
sudo rm /etc/update-motd.d/90-updates-available
Aquí hay un pequeño ayudante que mide el tiempo de cada guión:
$ for f in /etc/update-motd.d/*;do echo $f;time $f;done
/etc/update-motd.d/00-header 0m0.007s
/etc/update-motd.d/10-help-text 0m0.005s
/etc/update-motd.d/90-updates-available 0m49.163s
/etc/update-motd.d/91-release-upgrade 0m0.152s
/etc/update-motd.d/98-fsck-at-reboot 0m0.015s
/etc/update-motd.d/98-reboot-required 0m0.003s
(output reduced to the relevant parts)
pam_krb5.so se configuró para adquirir tokens AFS para un shell inexistente que tenía un tiempo de espera de 30 segundos que detenía cualquier autenticación usando ese módulo, no solo SSH. Se eliminó eso y la autenticación ocurre mucho más rápido.
Si su servidor ssh tiene activado el mapeo de DNS inverso, podría ser la causa de la demora, busque VerifyReverseMapping
en el /etc/ssh/sshd_config
archivo del servidor.