If a system provide n bits of security, it is known that the best possible attack against the system would be 2^n (security parameter). However, why are the key sizes of some cryptosystems much larger than their security parameters? Is it because these cryptosystems have a weak and vulnerable algorithm?
This can be either a philosophical question or a empirical question, but answer to both these sides can be similar.
First, the title is correct, higher key sizes corresponds to a higher security level. But that's within the same cryptosystem.
Second, public-key cryptosystems are based on mathematical problems, whose solutions admit more efficient cryptanalytic algorithms than brutal-forcing their symmetric-key counterparts:
- RSA has GNFS,
- Lattice-based ones have BKZ,
- Hash-based signatures trades total number of messages that can be signed with signature size.
Elliptic-Curve Discrete Logarithm comes the closest to comparable with symmetric-key crypto, with Pollard's rho giving half the security level against the order of the base point of the elliptic curve group.
Third, even symmetric-key algorithms have hidden costs that people often assume only public-key algorithms have.
For example, the size of the key schedule of a block cipher, the number of rounds of a permutation, the total number of pre-computed constants, etc.