Hint from securebadshah on superuser.com here
Probably the reverse DNS resolution (server trying to get client’s name given IP) is taking time. Can you check if /etc/ssh/sshd_config has setting “VerifyReverseMapping yes” ? Set it to “VerifyReverseMapping no” and check if helps.
Edit: It seems VerifyReverseMapping is now deprecated and useDNS is the new configuration in the sshd_config.
Adding a “useDNS no” line to /etc/ssh/sshd_config made my ssh login via Putty happen much faster.