If you are able to connect to that host using the command line ssh client, then try using Net::OpenSSH instead of Net::SSH::Perl.

Net::SSH2 may also be another good alternative.