Long place and route after adding logic lock regions

What device? Sadly, the larger devices(Stratix III and SIV) are commonly requiring a 4-bit OS. Do you have physical synthesis turned on? What is your fitte set to(Standard, Auto or Fast). What is your main clock timing requirement and how easily do you meet it? Can you run your design at a slower rate during testing?

One other thing is to look through the fitter messages and see how much time is spent in placement, physical synthesis and routing. In general, routing should be a small portion, but route intensive designs and/or full designs can skew that.