There are a myriad of possible causes. I've had a Solaris host sending an ident back to the client and timing out on the response. A google search shows others.

I'd guess that you get the same delay when using ssh from the command line. Try ssh -v -l user host to see what is happening. Multiple vs can be specified to get more and more debug output.