Stolen credit card numbers are a fact of life if you use your card much. My wife and I put better than $50,000 a year on credit cards (includes groceries and utilities) and have had our cards compromised three times in the past couple of years. Never have found how it happened. Most times the credit card companies caught it before we saw the bill, though once we found $19.95 for "Amazon Prime" charges. Turned out the perp had put that card on half a dozen Amazon accounts but had made only the one charge.
Replacement cards are no big deal except for having to learn a new number for online purchases. Only hassle was the time my card company called the evening before I had a flight across the country. No problem - they delivered my new card the next day to my son's home in California.