Starting from openssh 7.8 the default format for private keys has changed from PEM to OpenSSH:
That means that private keys generated with the referenced command:
(ssh-keygen -t rsa -b 4096)
are no longer generated as PEM format. Lot’s of online services do not accept this format yet CircleCI, GitHub are some of the services that have issues with this new format..
PEM format can still be generated using:
ssh-keygen -t rsa -b 4096 -m PEM