Ah, thank you. They were probably generated and exported with puttygen indeed.
Is there a way to load and re-export them to adhere to the correct format? (provided that this will keep the fingerprint used in ~/.ssh/authorized_keys unchanged - otherwise I will regenerate them from openssl and redeploy, something I would like to avoid because I have not automated that part)
You can use sshpk-conv for that task, available on Debian-like distros at the node-sshpk package, like this: sshpk-conv /path/to/your/private/key -t ssh -p.