True but a server that wants to "deanonymize" you can just reject each key till he has all the default keys and the ones you added to your ssh agent.

You can try it yourself [0] returns all the keys you send and even shows you your github username if one of the keys is used there.

[0] ssh whoami.filippo.io

It does, and there's typically a maximum number of attempts (MaxAuthTries defaults to 6 IIRC) before the server just rejects the connection attempt.

Modern sshd limits the number of retries. I have 5 or 6 keys and end up DoSing myself sometimes.