Not a solution (sorry), but an observation-that error sounds oddly familiar. Did the system being contacted update their version of OpenSSH from 5.x/6.x to 7.x? And what is the version of your Net::SFTP and Net::SSH::Perl? OpenSSH 7.0/7.0p1 was released 2015-08-11, with Net::SFTP and Net::SSH::Perl versions 1.39 and beyond being released after that date. My thought is that perhaps a newer version of those modules might also be an option (if you can't get a satisfactory answer to your primary question, but make sure to test first!).

Hope that helps.

Update: 2019-04-10
s/Net::SFTP/Net::SFTP and Net::SSH::Perl/g
s/that module/those modules/g