Check your line endings!

None of the other answers helped my issue. I encountered this issue when the line-endings on the private key file were not UNIX style line endings.

Open your private key (i.e. C:\Users\user\.ssh\id_ed25519) in a code-editor such as vscode and ensure that it says LF in the bottom right.

If this isn't the case and you see CLRF, click on it to change it to LF before saving. Or see other methods of changing the line endings for a file.