I agree that it is a problem. It probably makes sense to go through the transaction history of the wallets that one owns and see which wallets are "tainted" by communication with KYCed CEXes, then move the crypto from the tainted wallets to new ones. If the move is done through an intermediary privacy coin on some DEX, then it should be rather difficult if not impossible to connect the "tainted" wallets to the new ones. In most countries taxation is done only when selling crypto for fiat, so exchanging crypto for crypto should not involve additional government taxes/fees, although it will cost some network fees.