When I was working at EFF, I started writing (but never finished) a couple of essays along the lines of "the degree of trackability of mobile phones is an unfortunate accident, and we should fix it".
It basically comes from routing requirements (especially to receive incoming phone calls) combined with billing requirements (to make people pay for their connectivity) combined with the empirical requirement to see which base station a device is connected to, and which other base stations can see it at a given moment.
If you aggregate all of that data, then you know a (geographically moderate-resolution) complete history of where almost all people have been at almost all times, and patterns of their habits and whom they probably recurrently spent time with.
Not all of this data has to be collectable, because these things could be disaggregated by introducing different protocol layers. For example, you could pay the mobile company for data connectivity, but use cryptographic blinding mechanisms so that it doesn't know which specific subscriber obtained connectivity at a particular place and time. (Those blinding mechanisms could be implemented inside of SIM cards, so the SIM card's task is to cryptographically prove "I am a SIM card of a current paying subscriber of carrier X" rather than "I am SIM card number 42d1b5c0".) You could have device hardware IDs be ephemeral rather than permanent. Actual messaging and call services could all be "over the top" (as phone industry jargon puts it), provided by people who are not the phone company itself.
This disaggregation is a straightforward improvement from a privacy point of view because it prevents companies from knowing things about you that they didn't need to know in order to provide services.
Meanwhile, in the world we live in, we see governments trying to make it harder to make phones less trackable, by putting legal restrictions on changing hardware addresses, or requiring legal ID in order to establish service. I imagine that an additional cryptographic indirection layer in SIMs to prevent carriers from linking a permanent identifier to a network registration (or specific data use) would also be banned in some places if it were invented.
This shouldn't be inevitable. One thing that made me think about this was when there was a little scandal (which I was a small part of) about companies tracking device wifi MAC addresses for commercial purposes. There was a little industry that would try to recognize people and build commercial profiles based on recognizing that the same device was present (in fact, at the time, even if it didn't actually connect to the wifi -- because a typical wifi-enabled mobile device was sending broadcast wifi probe packets that included its MAC address). So Apple was like "this is a bad use of MAC addresses, which only exist to distinguish devices that happen to be on the LAN at the same time, and perhaps to allow network administrators to assign permanent IP addresses to specific devices", and they made iPhones randomize wifi MAC addresses for some purposes, mostly fixing that particular issue.
We could think just the same way about GSM networks: "these identifiers exist for specific protocol reasons; using them for device or user tracking is an abuse that should be mitigated technically".