A couple of questions that will help decide the easiest/best way to do it:
What is the current load on the +5 volts and is it constant? If it is pretty constant we could sense the current from the battery with a simple circuit. Also this might allow us to put the filter cap on the other side (right) of the 1N4002 diode and make it smaller. Otherwise just a big cap on the 12 volts would help. Also make sure the 12 volts for your circuit comes from the source not from somewhere in the string of "stuff" (pumps and such).