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