OpenSSH version 7.8 and greater default to generating keys with the OpenSSH format. This format is incompatible with versions of net-ssh < 5.1.0. Once net-ssh >= 5.1.0 ships with bolt rsa keys in the OpenSSH format should be usable.
Docs update:
http://docs-internal.puppet.com/docs/bolt/dev/bolt_new_features.html#rsa-keys-with-openssh-format-1-11-0
(FYI this^ is the preview site. I also updated production, but it's taking its sweet time building there.)
In what version is this resolved? I'm running 1.26.0 and it still has this problem.