I've played around with Net::SSH::Perl, and my impression was that it was just too slow. There aren't many things where the perl implementation is too slow for me, but this was one of them. I've used openssh in batch mode or driven by Expect.

Do your connections work with a regular SSH client?

Is your ultimate goal a script that determines if the SSH server is running? If so, you could probably just connect an unencrypted TCP socket and read the SSH version info (or lack thereof). If you need to make sure the SSH server is functional, IE you need to log in, you might consider running ssh in batch mode with ssh keys or using expect.