We don't, and that sucks. But it's not a binary choice between "you can carry your phone everywhere" or "you can avoid having your movements stored in a database indefinitely". There are other options that we as a society could choose, if we could get our acts together.
Sure, the opsec ideal is that you don't have to trust other parties in the first place. But honestly, for the vast majority of people, that sort of thing doesn't matter, and having strong, readily-enforced privacy laws would be more than sufficient to keep people safe and secure.