The Romulans have to have some way of going faster than light or they would not get anyway let alone be able to start a d earth/romulan war!
But as discussed, this is a completely separate issue from whether the ship
in "BoT" has FTL or not. This particular vessel could be incapable of interstellar warfare, but this is of zero relevance because the vessel is vital in the first step towards interstellar warfare: breaking out of the chain of Earth fortresses. That part can be done by a sublight vessel, in the model where the distances on that mysterious map are very short.
It's only "The Deadly Years" that gives this ship type significant FTL capabilities, certainly enough to discredit the "BoT" idea that the hero ship could run rings around the Romulan type. Evolution of the design or not? Well, even in "BoT", the hero ship does not
outfly the enemy by much.
Was it ever clearly stated that the Klingons obtain their cloaking device from the Romulans?
It was never even clearly stated that there would have been an alliance between the two; the closest they ever come is in "Reunion", where Riker contemplates the possibility of a "new" alliance between the powers as the consequence of Duras duplicity.
The Dominion also possessed cloaking devices aboard their ships
But did they? We never, uh, saw
an invisible Dominion ship. This IMHO is good indication that they indeed operated cloakships, but it's certainly no proof.
Jem'Hadar invisibility works very well at medium distances, and can be used to hide people, their clothing and their weapons alike, but whether it could hide ships in space...
Oh, and almost forgot:
remembering references to "praetor" in TNG
But there are no references to Praetor in TNG.
The highest leader referred to in TNG, apart from the obscure "Romulan Empress" thing, is the Proconsul. His exact slot in the hierarchy is unclear. In Roman terms, he'd be the Consul's representative in the provinces, the Consul being the very highest authority in the Republic; the representative's title survived the transition to the Empire and the discontinuation of the Consul position.
DS9 is the show where Praetor is finally mentioned, in this intel briefing:
"Neral. Formerly Proconsul and now Praetor of the Romulan Star Empire. Neral's ascension to the top post was confirmed by the Continuing Committee a little over a year ago."
Whether "the top post" means head of state or just what it says, a top post (that is, a highly placed job among others) is not semantically clear from the above. Again comparing to the Roman model, a Proconsul might become a Praetor; getting to serve as Proconsul would usually mean he had already been Consul previously, so any career move would be a move down anyway, and Praetor would be an attractive option. (In practice, you'd have to be a long-lived Romulan to enjoy such career succession, though.)
In ST:NEM, Shinzon also assumes the title Praetor, through assassinating and succeeding another Praetor who presided over Senate sessions. We don't really learn whether Shinzon declared himself the absolute top leader, or whether he upheld the usual coup tradition where the Colonel who topples the civilian government just declares himself General...