How can SSH server know private key is incorrect if passphrase havent been provided yet?

While you've encrypted the private key, the public key is still readable. SSH authentication with the "publickey" method works by having the client send each potential public key to the server, then the server responds telling the client which key is allowed. If one of the keys is allowed, then the client must decrypt the private key to sign a message, proving ownership of the private key.

In your experiment, the server responded saying that none of the provided keys was allowed for your username, so there was no need to decrypt a private key, authentication had already failed.

During connection client will sent successively fingerprint of all availables keys to server.

When server signal to client a valid key found, client will use them, then ask for passphrase if needed.

Try to run ssh with debug option:

ssh -o LogLevel=DEBUG3 user@dest

look for fingerprint with

ssh-keygen -l -f .ssh/id_rsa

For checking authorized_keys, line by line:

while read line;do
    ssh-keygen -l -f <(echo "$line")
  done <.ssh/authorized_keys