Upstream OpenSSH are flagging that they are about to drop support for the "ssh-rsa" method:
> It is now possible to perform chosen-prefix attacks against the
> SHA-1 algorithm for less than USD$50K. For this reason, we will be
> disabling the "ssh-rsa" public key signature algorithm by default in a
> near-future release.
Better alternatives are available, even with the same keys on disk. OpenSSH 7.2 or newer is ideally required.
RHEL 7 has 7.4, so it's fine. But RHEL 6 has the ancient 5.3 so it will not be possible to connect to such systems in the future.
We need to consider if we should just follow upstream and drop support, keep supporting it despite upstream, or add an option to re-enable it if users need to.
We also need to consider longer support for ssh-rsa in our ssh-keyscan as older clients might still be used.
OpenSSH only talks about host keys, but I would guess that public key authentication is also affected in the same way.
Also note bug 5539 for 4.5.0 where ssh-dsa support was dropped. We dropped support right away in the client, but kept support in keyscan.