Slow SSH Authenentication

I have set up an ssh server at my home from the default debian repository. Unfortunately, remote connections were quite slow, the authentication required about 30 sec. I tired to start the ssh client in verbose mode:

$ssh -v user@host
...
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: Roaming not allowed by server
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received

And after the last line it was hanging for a while. I suspected that it could be related with DNS lookups, so I added the following line into the server's sshd_config file:

UseDNS no

After this the restart of the ssh server was required.

#/etc/init.d/ssh restart

and the problem went away...