BIN attacks are becoming way, way more common, unfortunately, and about as far as you can go to protect yourself is lock the cards you aren't using. I've worked on the issuer side of trying to combat a BIN attack, and it's extremely frustrating (on top of it costing the FI maybe tens of thousands of dollars to cover the fraudulent charges). Issuers can't require that merchants ask for CVV or other identifying information such as address or ZIP. That means that, if fraudsters can get a good card number and exp date through brute forcing, they just need to use it at a merchant that only asks for those two things. The pizza place you mentioned is probably such a merchant.
The good news, so to speak, is that BIN attacks are usually a massive fraud attempt on basically all of an FI's cards that share that BIN, so if Redstone is experiencing a BIN attack, then they're well aware of it and I'd expect you should be able to get your money back without too much hassle. They would have had a large number of attempted fraudulent transactions at that pizza place, and the one on your card wouldn't have been the only one to go through before Redstone's anti-fraud algos blocked that merchant.
