If I try to connect to a server without passing a valid passphrase for my key, it says "Permission denied (publickey)" This message is very vague and unhelpful. I suggest at least appending a suggestion, like "Did you specify the correct passphrase, if needed?"
I don't think we'll be changing this message. Any suggestion runs the risk of being inaccurate, for example yours runs the risk of leading people to assume that a different public key might work for a destination that would never accept them. The current message is succinct and accurate as to what has happened. More detail is available via the verbose option if needed, but fundamentally the client is not in a position to guess why.
OpenSSH 9.3 has been released. Close resolved bugs