Key strengths, and their equivalences, become meaningless when they reach the zone of "cannot be broken with existing and foreseeable technology", because there is no such thing as more secure than that. It is a common reflex to try to think of key sizes as providing some sort of security margin, but this kind of reasoning fails beyond some point.
Basically, the best known algorithms for breaking RSA, and for breaking elliptic curves, were already known 25 years ago. Since then, breaking efficiency has improved because of faster computers, at a rate which was correctly predicted. It is a tribute to researchers that they could, through a lot of fine tuning, keep up with that rate, as shown on this graph:
(extracted from this answer).
The bottom-line is that while a larger key offers longer predictable resistance, this kind of prediction works only as long as technology improvements can be, indeed, predicted, and anybody who claims that he knows what computers will be able to do more than 50 years from now is either a prophet, a madman, a liar, or all of these together.
50 years from now, the optimistic formula given in the answer quoted above ((year - 2000) * 32 + 512) means that, at best, RSA records could contemplate approaching 2592 bits.
The conclusion is that there is no meaningful way in which 3000-bit and 4000-bit RSA keys could be compared with each other, from a security point of view. They both are "unbreakable in the foreseeable future". A key cannot be less broken than not broken.
An additional and important point is that "permanent" keys in SSH (the keys that you generate and store in files) are used only for signatures. Breaking such a key would allow an attacker to impersonate the server or the client, but not to decrypt a past recorded session (the actual encryption key is derived from an ephemeral Diffie-Hellman key exchange, or an elliptic curve variant thereof). Thus, whether your key could be broken, or not, in the next century has no importance whatsoever. To achieve "ultimate" security (at least, within the context of the computer world), all you need for your SSH key is a key that cannot be broken now, with science and technology as they are known now.
Another point of view on the same thing is that your connections can only be as secure as the two endpoints. Nothing constraints your enemies, be they wicked criminals, spies or anything else, to try to defeat you by playing "fair" and trying to break your crypto upfront. Hiring thousands upon thousands of informants to spy on everybody (and on each other) is very expensive, but it has been done, which is a lot more than can be said about breaking a single RSA key of 2048 bits.
The cipher/algorithm used for ssh keys is independent of the algorithm/ciphers used for encrypting the session/connection.
So a faster key algorithm will only speed up operations relating to key generation and validation, i.e. authenticating and establishing a session.
For faster or more secure transfer speeds, you can tune the preferred Cipherssshd_config-c cipher_spec
You can test on your own machine how for example how RSA 1024, 2048 and 4096 compare in that regard with ed25519 using openssl speed rsa1024 rsa2048 rsa4096 ecdsap256 ed25519
sign verify sign/s verify/s
rsa 1024 bits 0.000078s 0.000006s 12852.6 175638.7
rsa 2048 bits 0.000519s 0.000016s 1926.4 62959.0
rsa 3072 bits 0.001570s 0.000033s 636.8 30670.3
rsa 4096 bits 0.003496s 0.000055s 286.1 18200.7
256 bits ecdsa (nistp256) 0.0000s 0.0001s 41044.8 16044.8
253 bits EdDSA (Ed25519) 0.0000s 0.0001s 21079.9 9383.2
Yes, Ed25519 is still secure. The paper describes an attack against hardware processing Ed25519 signatures. It is not a cryptographic attack against the algorithm itself. As explained here, a fault attack (also called a glitching attack) involves trying to confuse a processor while it is processing cryptographic material to cause it to glitch in a way that leaks internal information sufficient to reconstruct the private key. Unless someone is hooking up electrical probes to your CPU, the attack does not affect you at all.
The attack involves hooking up a device to the CPU and "glitching" it, for example by feeding it too much or too little voltage at specific times. If the glitch occurs while cryptographic material is being processed, it is possible to discover information about the key by observing the results of the glitching. It is a very invasive procedure, as you can see in this photo of the attack being performed:
From the text describing this picture:
We demonstrated it on an Arduino Nano, using the Arduino Libs’ Crypto Ed25519 implementation and simple voltage glitches. We were able to cause single byte random errors at the end of the computation of H(R,A,M), allowing us to efficiently brute-force the error location and value, thus recovering half of the secret key.
So why is this attack newsworthy? The answer is simply that not every use of Ed25519 occurs on a machine that you have full control over. For example, secure embedded devices, such as smart cards, might fall into adversarial hands. These devices are designed to be secure and not reveal their private key even if you have physical access to them, so it would be bad if you could steal the private key just by monitoring the device while you feed it an incorrect voltage! This attack does not mean that every use of Ed25519 is doomed to be vulnerable to a fault attack, just that each implementation must apply mitigations to avoid this issue in situations where it is relevant.
If I remember correctly, it is simply an issue of performance. Remember, HostKeyAlgorithms
The ECDSA algorithm is faster than RSA, and small key sizes are faster than large key sizes, when the default was changed in 5.7, the changelog specially referenced performance reasons, See the first feature item.
NIST keys are probably preferred over ED25519 for compatibility reasons, I have had to generate NIST keys after Curve25519 based keys after finding the server did not support them, so that makes total sense. Curve25519 based keys are probably more secure, unless you are asking NIST, then they say the are equally secure.
Since these are just default options, you are of course free to change them or force a specific algorithm, I have forced 3072-bit RSA for my default host key method. Remember, this is a selection option, if a key type on the list does not exist, it will not be used. If you only have RSA keys in your configuration, all the EC options will be skipped, you can delete them at will.
If you are using SSH for transport and you have control over the app and server, you can just generate the 1 host key you want and be done with it, and ignore the configuration options, since they will not matter.
It is not possible to double security level of Ed25519 any trivial way. Instead, doubling security level requires using another curve that is approximately 512 bit curve.
In systems compliant with RFC 7748, i.e. some of IETF specifications, there is Curve448 curve (Ed448-goldilocks). It is almost twice as strong as Curve25519 (its strength is 224 bits). This is often convenient alternative, because it is already available on some of the systems.
Widely deployed alternatives that are 256-bit security: Of course there are also BrainpoolP512 and NIST P-521 curves, which in theory provide 256 bit security. However, BrainpoolP512 and NIST P-521 are not considered to be as good as Ed25519 in all aspects possible (see e.g. https://safecurves.cr.yp.to/).
M-511 and E-521 are curves similar to Curve25519, which offer around 256-bit security level. However, because it is wide spread to consider security level 128 - 192 sufficiently strong for now, so larger curves are not used often in practice. For instance, NSA suite B site suggests that they consider 192-bit security level (i.e. 384-bit elliptic curves) to be sufficient to protect TOP SECRET materials.
Any optimized curve specific implementation of elliptic curves, such as the implementation of Curve25519 in lib sodium/NaCL is hard to replace efficiently with curve of different size. However, the API level of lib sodium/NaCL allows easy replacement of cryptographic primitives. Therefore, the "right" way to "hack libsodium/NACL" would probably be to provide the necessary curve(s) implementation(s) in API that is compatible with NaCL API. This usually requires use of different implementation rather than tweak of code implementing Curve25519. And some API work to adapt the API, as most Elliptic Curve implementations have APIs somewhat different from API in libsodium/NaCL.
Yes, Ed25519 provides the existential unforgeability property. There is a nice work that studies the different variants of Ed25519 signatures
https://eprint.iacr.org/2020/823.pdf
As specified in that document, the different variants of ed25519 provide different security properties, but all are existentially unforgeable under chosen message attacks.
Indeed, as you point out, if an adversary could forge valid signatures to messages not signed by the key owner, the security of the blockchain could be compromised.