Not every time. In my current place the cable is stapled directly to the studs so it would require gutting basically everything to replace all of it. Luckily most of the runs go to places that make sense but I’ll never be able to upgrade from CAT5e.
That’s how my house is as well. The builder used CAT5 for all of the phone runs. Fortunately it’s a one story with easy attic access. I’ve rerouted many of them to a closet (the originally all terminated outside near the electrical panel) and ran a few more by drilling through top plates in the attic. I don’t have jacks everywhere I’d want, and most of the cable is CAT5, but it generally hasn’t been an issue. Most of the lines seem to support gigabit speeds.
In my previous house an upstairs leak resulted in a downstairs ceiling coming down which was a boon for wiring up most of the house and adding in ceiling speakers and can lights.
In some jurisdictions, every wall will have a horizontal 2x4 about half-way down the wall. Drilling through the top-plate will get you started, but you'll need a special 4' long drill-bit to make the second hole you need in that 2x4. It's kind of fun to drill with such a long bit.
