I had this problem where it took way too long time for the prompt to appear when using ssh to remote server. And b.t.w. I am using my public ssh key. The GSSAPI authentication was timing out, and I'm not not relying on it.
To turn it off edit the /etc/ssh/ssh_config file with your favourite editor, I use VIM
sudo vim /etc/ssh/ssh_configEdit this line and change from yes to no
GSSAPIAuthentication no