Dans un cas très similaire, il s'agissait de l'un des scripts update-motd.
Ce qui suit a fait l'affaire :
sudo rm /etc/update-motd.d/90-updates-available
Voici un petit assistant qui mesure le temps de chaque script :
$ 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 a été configuré pour acquérir des jetons AFS pour un shell inexistant qui avait un délai d'attente de 30 secondes arrêtant toute authentification à l'aide de ce module, pas seulement SSH. Cela a été supprimé et l'authentification est beaucoup plus rapide.
Si votre serveur ssh a activé le mappage DNS inversé, cela pourrait être la cause du retard, recherchez VerifyReverseMapping dans le /etc/ssh/sshd_config fichier du serveur.