This appears to be a DNS issue
There are a couple of very simple ways to fix that:
- add “UseDNS no” to /etc/ssh/sshd_config
- add the client’s net address to the server’s /etc/hosts
login via ssh
nano /etc/ssh/sshd_config
Add lines
#fix for slow SSH session start
UseDNS no
Save and exit
Service sshd restart
Creds: http://www.turnkeylinux.org/blog/slow-ssh