It's how the SSH protocol itself works. When the client connects to a server, it sends the (remote) username and then a series of public keys. If the server will accept the current public key, it asks the client to authenticate with that key to show that you hold the private key; if it doesn't, it says 'try again'.
This means that a malicious client with just the public key can probe to see if a server will accept a given username/public key combo. If the server does, it will challenge you to authenticate that you hold the private key (which you'll have to fail, since you don't have it).