I recently generated a new SSH key in the ed25519 format.
The public key is only 69 bytes long while my old RSA key is 373 bytes.

From my perception ed25519 is the more recent and secure format.

So why isn't longer better here?

No, longer is not better.

Let me explain. In symmetric cryptography, keys are just bunches of bits, and all sequences of bits are valid keys. They have no internal structure. Provided that you use decent algorithms, the best possible attack on a key for symmetric encryption is brute force: the attacker tries all possible keys until he finds the right one. If the key has n bits, then there are 2n possible keys, and the attacker, on average, will find the right one after trying half of them, i.e. 2n-1. Longer keys thus make brute force harder; in that case, longer is better.

(Note that there is a limit to that; when keys are sufficiently long that brute force is no longer feasible, increasing the key length does not make things "more secure" in any meaningful way. So, for symmetric keys, longer is better until they are long enough, at which point longer is just longer.)

RSA and EdDSA relate to asymmetric cryptography where things are completely different. A key for asymmetric cryptography is a mathematical object that has a specific internal structure; breaking the key consists in unravelling that structure, and can be done a lot more efficiently than trying out all possible private keys. Note the two points:


Against brute force, what matters is not the length of the public key, but that of the private key, since what the attacker wants is the private key, not the public key.
Brute force is not the most efficient attack against keys used in asymmetric cryptography.


For RSA keys, attack succeeds by factoring the modulus. Integer factorization is a long-studied problem; with the best known algorithm, breaking a 2048-bit RSA key (i.e., a RSA public key whose modulus is a 2048-bit integer) requires about 2110 or so elementary operations.

For EdDSA keys, the public key is a point P on an elliptic curve, such that P = xG where x is the private key (a 256-bit integer) and G is a conventional curve point. The best known algorithm for recovering x from P and G requires about 2128 elementary operations, i.e. more than for a 2048-bit RSA key. In general, to break a n-bit elliptic curve public key, the effort is 2n/2.

Breaking either key is way beyond that which is feasible with existing or foreseeable technology. But in an "academic" viewpoint, the EdDSA key is somewhat stronger than the RSA key; also, elliptic curves give you more security per bit (technically, we say that integer factorization is a sub-exponential problem).

See this site for more information on that subject.
