Ve velmi podobném případě to byl jeden ze skriptů update-motd.
Povedlo se následující:
sudo rm /etc/update-motd.d/90-updates-available
Zde je malý pomocník, který měří čas každého skriptu:
$ 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 byl nakonfigurován tak, aby získával tokeny AFS pro neexistující shell, který měl 30sekundový časový limit, který zastavil jakoukoli autentizaci pomocí tohoto modulu, nejen SSH. To bylo odstraněno a ověřování probíhá mnohem rychleji.
Pokud má váš ssh server aktivované reverzní mapování DNS, může to být příčinou zpoždění, vyhledejte VerifyReverseMapping v /etc/ssh/sshd_config soubor serveru.