If someone really wants to figure out who you are, they can do that by simply tracking the location of your IMEI. But you can establish a reasonable level of disconnectedness by simply not giving your phone provider your real name, address, or electronic payment info. This is completely impossible in many parts of the world, where you have to prove residency or citizenship to get a phone number.
Technically only the modem has to be changed, but in practice this means changing the whole motherboard. And that is usually not cost-effective, so in reality you simply get a new phone. Dual-SIM and SIM+eSIM phones have two IMEIs, one for each SIM slot.
Just to be clear, I actively discourage replacing your phone solely to get a new IMEI. That is an incredibly wasteful thing to do for a somewhat nebulous privacy improvement.