SSH key generated by ssh-keygen is not recognized by Paramiko: "not a valid RSA private key file"

For OpenSSH 7.8 up, you have to trick it. Run ssh-keygen -p [-f file] -m pem to purportedly change passphrase, but reuse the old one. Use -P oldpw -N newpw if you want to avoid the prompts, as in a script, but be careful of making your passphrase visible to other users. As a side effect this rewrites the keyfile (if not ed25519) in 'old' (OpenSSL-compatible and thus paramiko-compatible) format. (If you want to keep the new-format file, copy first.)

For older versions of OpenSSH just do ssh-keygen -p [-f file] WITHOUT -o.

Also, if you have (or get) it, the puttygen utility in the PuTTY suite from 0.69 up supports this format. In the Unix version, just do puttygen newfmtfile -O private-openssh -o oldfmtfile (again excepting ed25519). In the Windows version AFAICT you must use the GUI; load the newfmtfile and do Conversions / Export OpenSSH key .