5V relays are fine, I used 4.5V relays for the non-latching version with no problem.
The 9V regulator is used to limit supply voltage if the circuit is powered by greater than 9V... in most cases it will be running under-voltage and the 555 timer will drop another ~2V.
