$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:
After this the restart of the ssh server was required.
and the problem went away...