sshに関係なく公開鍵暗号一般での話と考えた場合、それぞれの方式で行える事は
なので、上位互換とは言えないでしょう。
SSHでの公開鍵認証で考えた場合、利用するのは署名のみとなります。
以下はSSHでの公開鍵認証に絞った話となります。
同等のセキュリティを提供するために必要な暗号鍵の長さは RSA 以下で
これは何を基準にするかによって答えが変わると思います。
ECDSAやEdDSAは利用する曲線により強度が変わります。
SSH で使われる Ed25519 の場合は Curve25519 という曲線を使い、この場合の鍵長は 256 bit です。
RSA で同等の強度と言われているのは 3072 bit なので、これを元にすれば Ed25519 の方が鍵長は短いと言えます。
この辺りの詳細については"等価安全性"で検索してみて下さい。
一方、RSA 4096 bit を元に考えた場合、Ed25519 は RSA 3072 bit 相当でしかないので、そもそも同等のセキュリティを提供するのは不可能という事になります。
2020/05/07追記:
見逃していたのですが、2020/02/25にRFC8709 が出た事によりSSHで使えるEdDSAとしてEd448が追加されました。これにより、RSA 4096bitよりも強度が高いEdDSA署名が使える事になります。
ただし、以下の問題は残ります。
- 現状ではEd448をサポートした実装がほぼ無い
- RSAのようにbit数が可変ではなく、256bit(Ed25519), 448bit(Ed448) の二種類しか無い
SSH の公開鍵認証の場合、併用するハッシュ関数の強度も問題になりますが、詳細については省きます。
暗号を破るための計算を行う際の計算量クラスは RSA 以上で
実際に署名の verification などを行う際の計算量クラスは RSA 以下
計算量オーダーはソートのように対象データが一定でない場合の比較には便利ですが、SSH の公開鍵認証、特に Ed25519 のように鍵長が一定で、署名対象のデータの長さもほぼ一定という状況のように、パラメータが一定の場合は計算量オーダーで比較するのはあまり意味がないと思います。
2020/05/07追記:
計算量オーダーで比較するのはあまり意味がないというのは、パラメータが固定なのだから実際の速度で比べた方がいいという意味です。
一例として手元の環境でopenssl speed
コマンドで比較してみました。
% openssl speed rsa3072 ed25519
Doing 3072 bits private rsa's for 10s: 2551 3072 bits private RSA's in 9.86s
Doing 3072 bits public rsa's for 10s: 128817 3072 bits public RSA's in 9.87s
Doing 253 bits sign Ed25519's for 10s: 238724 253 bits Ed25519 signs in 9.87s
Doing 253 bits verify Ed25519's for 10s: 71419 253 bits Ed25519 verify in 9.85s
OpenSSL 1.1.1d-freebsd 10 Sep 2019
built on: reproducible build, date unspecified
options:bn(64,64) rc4(8x,int) des(int) aes(partial) idea(int) blowfish(ptr)
compiler: clang
sign verify sign/s verify/s
rsa 3072 bits 0.003865s 0.000077s 258.7 13055.1
sign verify sign/s verify/s
253 bits EdDSA (Ed25519) 0.0000s 0.0001s 24193.7 7249.5
傾向としては、署名生成に関してはEd25519の方が圧倒的に速いですが、署名検証はRSA 3072 bitの方が速いという事になると思います。
この点からも上位互換とは言えないと思います。