I experience a lot of various problems with distance walking. As far as I have seen, fancy shoes or insoles do not make much of a difference. In some cases, this aid can help, but in some cases, it just reduces the symptoms of deeper issues.
The first thing to check - have you build the walking volume gradually? Maybe you just need more time to adapt via smaller walking volumes.
Else the chances are, that you do not have a perfect walking technique (to much impact of friction). You can make research on this topic on google and/or youtube. However, the best would be to hire a professional who can investigate this and advise. If you start investigating this topic, you will find out that almost nobody walks with "good" walking mechanics. However, walking is the most fundamental and important movement, so it is really worth to invest time into learning it correctly.
Some things you can try:
if you walk barefoot in an office building, can you hear your steps? If you hear impact or "friction" you probably have space to improve.
if you walk barefoot on fine sharp gravel a few hundreds of meters (or few kilometers), does it pain? If yes, you probably can practice that (not to get used to it!, but to learn how to reduce the friction and/or impact).
the same like 2., but on a hard smooth surface (concrete).
quite a nice tool could be some walking/running treadmill (they should have it in every gym). The treadmills tend to make every hard step very loud (like a hallway in an empty office building), however, on a treadmill you can safely walk barefoot for a long time (that is not possible in the most of places).
A good related article is this one: https://www.strongfirst.com/how-to-ruck/ - it is about rucking, but there is a part about footwear and "rucking technique" that apply for this topic also. Walking can be considered as a special case of rucking (0 weight rucksack).