Newer versions of OpenSSH attempt to reverse resolve client IP addresses. This can cause slow ssh connections if the client IP does not reverse resolve as the DNS request will be attempted multiple times and timeout each time.

To fix the problem, disable it in your /etc/ssh/sshd_config:

  UseDNS no