Unspecified GSS failure from SSH causes slow login

I SSH into one of my server, But I encounter this error, but instead I encounter the follow error. Eventually, after waiting about 15-20 seconds, I'm able to connect to. This was far too long for a LAN-based machine 

$ ssh -v ip_of_remote_server

.....
debug1: Unspecified GSS failure.  Minor code may provide more information
Unknown code krb5 195

debug1: Unspecified GSS failure.  Minor code may provide more information
Unknown code krb5 195

debug1: Unspecified GSS failure.  Minor code may provide more information
Unknown code krb5 195
.....

I was quite puzzled. Although I am using IP address of the server to ssh and have tweaked "UseDNS = no" at /etc/sshd_config. See Resolving Slow SSH Login, In addition, I'm doing SSH public/private key authentication. See Auto SSH Login without Password


But the resolution for this issue was easier than I thought. I just need to ensure /etc/hosts contains both the servers I am ssh from and to and it became very quick.

If you are using DNS instead of /etc/hosts, do take a look that your DNS settings at /etc/resolv.conf

Other Issues on SSH, you may want to read about

1. SSH Error : Permission denied (publickey,gssapi-with-mic,password)
2. Resolving Slow SSH Login