The Federation would win:
- The Treaty of Algeron would be nulled and have no standing. Thus, whilst the Romulans will have a brief advantage due to the cloaking device, there is nothing to prevent the UFP from obtaining its own cloaking tech. And we saw in The Pegasus that this is superior to anything (that we know of) the Romulans held.
- The Federation and Klingons are allies. And a major aspect of that alliance is the NATO-esque mutual defence clause. This is essentially why the Federation and Klingons were allied in the Dominion War. The Romulans would be hard pushed to combat and defeat both the Federation and the Klingons.