Whenever I've had to install Net::SSH, I've always broken down and installed the C library that Math::Pari is interfacing by hand. Then, I installed Math::Pari by hand. Then, I tried again. It's about the single worst module (other than possibly DBD::Oracle on a box without any Oracle installations on it) to try and install.