Not too long ago I was able to successfully use tsocks. See also the list of similar programs maintained by Debian for other alternatives.

Anyway, nowadays I would forget about Net::SSH::Perl and instead, use Net::OpenSSH that can use and external program (i.e. socat) to establish the connection to the remote server... though, it does not work on Windows.