Depends on which key is stolen. You can't update the certs on distributed users without some root certificate key. If that key is compromised, there is no trust root which the clients can trust anymore. The thief can revoke all the keys the original institution holds, so they have no path for changing keys.
To do that revocation, they'd have to be able to attack the update channel itself. And practically speaking, that attack is hard to pull off; you can probably successfully update most devices, which might be good enough.
