Slow SSH login SSH2_MSG_SERVICE_ACCEPT received

After installing new VM, my login to the server was with delay after entering the username.

The ssh -v logs shows as follow:

# ssh -v root@newserver 
...
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received

debug1: Authentications that can continue: publickey,gssapi-keyex,gssapi-with-mic,password

...

and delay were happening at SSH2_MSG_SERVICE_ACCEPT received debug line,

This server being recently installed, it even couldn't resolve its own hostname:

# ping newserver.example.com

^C

#

So for me I needed to add the new VM FQDN to dns server or to /etc/hosts file of the server:

# vim /etc/hosts

127.0.0.1   localhost localhost.localdomain localhost4 localhost4.localdomain4

::1         localhost localhost.localdomain localhost6 localhost6.localdomain6

10.18.20.32 newserver.example.com newserver

And issue resolved. 

Even though disabling useDNS in sshd config file was solved the issue only from Linux client to new server and I still had delay in login from Windows PuTTY.

# cat /etc/ssh/sshd_config |grep -i dns

UseDNS no