I do most all of my touring in Keen sandals including my Alaska trip & temps in the 20's(F). Pretty much all the time I wear them with wool socks. You can't beat sandals for comfort & drying quickly. Keens do however, provide more support and toe protection than the Teva.

BTW: I tried gore-tex covers and I ended up ditching them because my feet sweat so much inside.