in reply to Net::SSH::Perl and SSH protocols
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.
In Section
Seekers of Perl Wisdom