Sandals never worked for me for riding even when I lived in them pretty much all the time off bike (I mostly gave up on sandals even off bike after I could no longer by Alps, never found another sandal I liked as well). Maybe you just need to tinker with the adjustment of the straps? Maybe they just aren't for you? Maybe try different sandals (stiffer ones)? Maybe bigger pedal platforms? Maybe real bike shoes? Maybe something else?
Me, I much prefer my Sidi MTB shoes and they have worked very well for me as my only footwear on some tours or in conjunction with something else for off bike on others, but everyone needs to figure out what works for them. The answer may be different from tour to tour depending on the locale, mostly wrt what you use off bike (whether it is the same as your on bike shoes or something else).
Warning the following will be regarded as heresy by most folks...
Heck, on some tours I'd almost opt for road shoes and pedals (and may even do so at some point) if I was willing to change shoes when I wanted to walk any distance (I don't even mind walking short distances with big clunky Look cleats with Kool Kovers to save the cleats). It sounds crazy, but I have considered going with road shoes and a quick change to flip flops for off bike. My MTB shoes and pedals are great, but road shoes and pedals are even better for on the bike, just not so good off bike.