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