If a person had root on your KDC, then they had the ability to grab a copy
of your entire Kerberos database. While the database is encrypted with the
master key, a root user could have read the master key out of the stash
file, or even attached a debugger to the KDC process to read the master key
out of the KDC's memory.

So, this now becomes a question of what to do when every key in your
database is compromised.

When a user's key is compromised, the attacker can impersonate that user.

If a host key is compromised, then an attacker could generate forged service
tickets for that host with any user in the ticket.

However, the worst key to get compromised is the krbtgt key, as an attacker
could use this to generate a valid TGT for any principal in your realm!

The steps you should take depend on the exact circumstances of the incident
and your local site policy. However, it's important to keep in mind that the
worst-case scenario is that your realm would need to be completely re-keyed.

If I personally was responsible for our KDC and this situation happened to
me (a person who had root on our KDC left under questionable circumstances),
I would immediately change the key for the krbtgt and the admin principals,
and force a global user password change over some period of time (assuming
we weren't expiring passwords at this point).

As a side note, a compromised master key isn't quite as bad as one would
normally fear. The master key is only used to encrypt the Kerberos database
and as a seed for the random number generator. As long as access to your KDC
is secure, an attacker can't do much with the master key.