Should I be using ECDSA keys instead of RSA?
For "bits of security", see something like this comparison.
For why ECC over Prime Field gives you security equivalent to half the bit size, while RSA and FFDHE give much less security per-bit, it's because the strength of RSA against the best known attack is calculated like this while the strength of ECC against best known attack is calculated like this.
The NIST P-256/384/521 curves are safe, and ECDH over them and the ECDSA algorithm are safe, but they are a previous generation of curves and algorithms. The advancement since then has been in three areas:
- Choosing a curve in a non-arbitrary way so that it is much more "nothing up my sleeve", to ensure the curve isn't one in which the NSA have a way to break crypto faster than brute force, which people worry about. You shouldn't worry IMO, for these reasons, but some people consider it a reason to upgrade from NIST curves.
- Ease of implementation, or equivalently, chance of a random implementation turning out to be secure.
- Performance.
The state of the art currently and the ECC systems recommended by everyone is X25519 ECDH (Curve25519 ECDH) and Ed25519 Digital Signatures / long term keys. Basically everyone agrees they are better than NIST P-256 ECDH and ECDSA. A drawback is that they are not supported in HSMs and hardware tokens like Yubikeys.
If you can use software SSH host keys, you should use Ed25519 host keys.
If you can use software SSH user keys, you should use Ed25519 user keys.
If you can use curve25519 key exchange, you should use it.
The fallback for 25519 is NISP P-256. The fallback for P-256 is RSA and FFDHE, with at least 2048 bits (up to 4096 bits), both with SHA2 and not with SHA1. RSA with SHA1 and FFDHE with SHA1 are not allowed anymore.
Note that all of these systems will fall if and when someone builds a big enough quantum computer. To solve this problem, people are working on "post quantum" replacements that will be secure even if the adversary has a quantum computer. NIST is waiting for PQ Crypto competition to end, issue recommendations and standards, hardware crypto device vendors to start selling PQ devices, and everyone will upgrade to the PQ algos.
Because this upgrade is imminent (in NIST time frames), they have decided to not urge everyone to upgrade from P-256 to Curve25519, or even from RSA to ECC. NSA basically said to save your budget for the PQ upgrade.
People using SSH keys not stored in hardware devices have upgraded though, and everyone has upgraded ECDH because ephemeral keys don't need hardware secure storage.
Even the ossified TLS ecosystem (not SSH) has upgraded to X25519 ECDH, though they can't upgrade to Ed25519 because there are no HSMs available and they basically decided to wait for PQ crypto standards and HSMs. The standards / RFCs are available, it's just nobody uses them.
ECC keys can be much shorter than RSA keys, and still provide the same amount of security, in terms of the amount of brute force that an attacker would need to crack these keys. For example, a 224-bit ECC key would require about the same amount of brute force to crack as a 2048-bit RSA key. See https://wiki.openssl.org/index.php/Elliptic_Curve_Cryptography for more info.
To be complementary to other answers, just let me share a nice table taken from NIST SP 800-57:
Basically, what you can see here is that you would need RSA 3072 bit vs ECDSA 256-383 bit to achieve the same level of security strength (128-bit).