Why do HSMs make it harder? Algorithm changes are rare, and when they happen you'd need to upgrade all the clients that are working with the keys or certificates, so at that point it's a question of software rotation rather than key rotation. The HSM shouldn't be your biggest problem at that point.