At least in the US, having your card number stolen is such a small deal that it hardly seems worth worrying about. Just keep an eye on your statement, which you should really be doing anyway. You don't have to pay for charges you didn't authorize. In my experience, the card issuer typically detects the fraud automatically.
However I still changed my credit card since it was in the Linode database.
I considered changing registrar. But I really can't know to which one I can go. How do you know they won't be (or already are) compromised?