Net::SSH::Perlが遅いときは

Math::BigInt::GMP をインストールしたら速くなったよ！

正確に言うと、Net::SSH::Perlが必要としているCrypt::DHが必要としているMath::BigIntは、Math::BigInt::GMPかMath::BigInt::Pariがインストールされてないと激しく遅い、ということぽいす。

Math::BigInt::GMPなし
  real    0m31.984s
  user    0m31.730s
  sys     0m0.036s

Math::BigInt::GMPあり
  real    0m0.781s
  user    0m0.524s
  sys     0m0.032s