sudo echo "UseDNS no" >> /etc/ssh/sshd_config

This prevents the server from doing a reverse DNS lookup on the IP address, which apparently takes forever sometimes.