Are you certain that the circuit runs at 9V? Perhaps the 9V battery is regulated to 5V to run the circuit, which would make life easier for you. Use a multimeter to check the actual voltage on pcb tracks or solder points.
But if this whole circuit ultimately operates a relay or something, it would be easier to replace the whole board with a new circuit that runs at 5V and has an Arduino and a new relay. So tell us more about what the current circuit does, perhaps with pictures or a diagram.