Timing requirements not met inspite of optimised design.

I have been using a design on Cyclone V device.

I use Quartus Prime 16.1.2 for compilaiton.

The resource and logic utilisation is not above 50 %.

What I observe is the timing requirements is not met for the system. I have checked the paths with slacks and improved the timing in those paths . But later again the timing is not met showing other paths which are not involving high logic / complex wiring.

The timing is achieved after number of trials with different initial placement seed in fitter settings. But it is a tedious to run multiple compilation of the system as it takes hours to finish compilation.

I have even tried different versions of Quartus. The behaviour is the same.

Is there an alternate solution for this situation to achieve timing without changing the design?