Are there any benefits for certificate based authentication over the other types of authenitication? When it is common to use it? If the certs are stolen everyone that have them cat authenticate to the system. Is this true?
The problems with passwords are that they are typically reused and easy to guess, so they are easy to compromise and one compromise often leads to multiple compromises. In a simplistic sense, a private key is just like a very long, very difficult to guess password, which makes brute forcing harder.
If the key is stolen, it's the same as a password being stolen and the same considerations need to be in place (is it used elsewhere?). If the certificate is stolen, in theory other keys could have been generated so yes, you need to re-issue every key associated with it. Typically though, if this happens, you've got bigger issues (how did this happen in the first place?).
See here for more discussion of the pros/cons.