The error message appears to be saying your client is trying: 3des-cbc, blowfish-cbc, and arcfour but the server is only using aes256-cbc. So you need to either modify the server to use e.g. 3des-cbc or modify your client to use aes256-cbc. If Net::SSH::Perl is shelling out to run ssh then check your ssh_config file (or sshd_config on the server).