No idea was going wrong with Net::SSH::Perl, but if you can connect using the OpenSSH client, its very likely you will also be able to connect using Net::OpenSSH

You could also use Net::OpenSSH::Compat::Perl that implements most of Net::SSH::Perl API on top of Net::OpenSSH.