You can sleep in a bed to regenerate. There are lots of beds in villages and towns.
As the quoted wise man said, you can do that. In the first city, you can just go the camp where the Legioneers are (The campfire, the pot, near their kitchen, etc.) get warm and sleep in their beds a bit.
Besides, if you already have Jahan as a companion, he can just heal up, I know it's annoying, but out of combat the cooldown is very minor.
