SSH slow at starting session

In a very similar case, it was one of the update-motd scripts.

The following did the trick:

sudo rm /etc/update-motd.d/90-updates-available

Here is a little helper which measures the time of each 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 was configured to acquire AFS tokens for a non-existent shell which had a 30 second timeout halting any authentication using that module, not just SSH. Removed that and authentication happens much quicker.

If your ssh server has reverse DNS mapping activated, it could be the cause of the delay, look for VerifyReverseMapping in the /etc/ssh/sshd_config file of the server.