I do not have a battery suggestion other than using button cells series / parallel to get the voltage and amps needed.

But why 5 volts? If this is PIC based there are many chips that will run at 3 volts and less if a 4 mhz osc is used. The current consumption is lower too at the lower voltages. Supporting circuitry may have a low voltage solution also.