Oh no, the mains phase and neutral can be pretty close to each other, 1mm is fine, if I remember rightly.
I think you've missed the point about why there should be 5mm between the mains and 5V. The 5V side is a non-hazardous voltage which is safe to touch and will be connected to lots of potentially uninsulated metal parts. Therefore the insulation between the mains and the 5V side needs to be very good. This is because there can be some pretty high voltage spikes on the mains (>2kV) and it's important to protect the user from them. The insulation between the live and neutral is not so important because if it fails the user won't receive a shock, if there's a high voltage spike, it'll just arc over for a split second and nothing bad will happen, the worst case is the fuse will blow.
Your new board layout is much better. The only traces I'd be concerned about are the ones on the opto-coupler next to the bridge rectifier but if you CAD package says they're 5mm away from the 5V tracks then don't worry about it.
What size are you aiming for?
What size is it now?
You could probably make it a little smaller whilst still keeping to the 5mm rule.