The goal: no host trusts an individual's key any more. Hosts trust the Shellius CA, people get certificates that expire, and the old keys are gone.
Do this one environment at a time, least important first.
1. Inventory what you have
Add your hosts to Shellius before changing anything on them — by hand, with bulk import, or from a cloud connector. Tag each with its real environment; that tag is what later decides whether approval is needed.
2. Bootstrap, keeping the old keys
Bootstrapping adds CA trust. It does not remove authorized_keys, so existing key logins keep working alongside certificates. This is your safety net during the migration.
3. Move people over
Create policies that mirror who legitimately needs what, then have people connect through Shellius for a week or two. Watch the audit log to confirm real work is happening over certificates.
4. Remove the old keys
Once nobody relies on them, empty the authorized_keys files. Shellius does not do this for you, deliberately — it is the one irreversible step, and it is yours to take.
Keep one way in that does not depend on Shellius
Hosts validate every certificate login against the Shellius API. If Shellius is down, those logins fail. Keep a break-glass credential — console access, or one sealed key — and test it.
Hosts you cannot bootstrap
Appliances, managed services and other people's machines cannot be made to trust a CA. Store their credentials in the Keystore instead: still central, encrypted and audited, but not short-lived.