The 16F628 can work with 3.0v to 5.5v, with a max current draw of 2mA.
Use a standard 7805 linear-regulator with a heat-sink and a few other components. It'll be inefficient as hell and not suitable for small spaces, but it's bulletproof otherwise.
It's best to choose the highest output voltage possible to minimize the wasted heat from the voltage difference between input and output.
Place a diode in series for a diode voltage-drop of 0.6 - 0.7v to bring it down below the 5.5v max. The batteries will decrease in voltage over time, but should die before they get to 3.7v?
Though if you'll be drawing very little current, get a diode that will conduct at as low of a current as possible, and possibly do tricks like this.
Given that 2-amp diodes don't need heatsinks like 2-amp transistors do, I assume the efficiency of this is pretty high? Though that's saying that a diode converts excess voltage into current which almost certainly isn't true.
Use a Zener Diode regulator, possibly stabalized with a transistor.