What prevents someone from spoofing their public key when trying to establish an SSH connection?


Recently I’ve been trying to learn the mechanisms behind SSH keys but I came across this question that I haven’t been able to find an answer to (I haven’t figured out how to word my question such that searching it would give me the answer).

Basically, we add our local machine’s public key to the server’s authorized_keys file which allows us to be authenticated automatically when we try to ssh into the server later on. My question is: what if someone takes my public key (it is public after all) and replaces their public key with it? When the "attacker" tries to connect to the server, what part of the process allows the server to know that they do not have the correct private key?

I read somewhere that for RSA, it is possible for a user (let’s say user A) to encrypt/sign a message with their private key, and then for others to decrypt this message using A‘s public key, thus proving that A is really who they claim to be. However, apparently, this is not true for all cryptosystems, where it is not possible to sign with a private key (according to What happens when encrypting with private key?, feel free to correct this information if it is wrong). In those cases, how does the server make sure that the user is really who they claim to be?