Seems long, but how much time is spent in:
Analysis and Synthesis
Fitter, which is broken up into:
- Placement
- Physical Synthesis
- Routing
(I'm assuming the other steps are negligible.) Note that you can get placement time, physicaly synthesis time and routing time out of the fitter messages. The biggest culprit I've seen for compile times going up is physicaly synthesis(Assignments -> Settings -> Fitter/Physical Synthesis options), and I try to avoid these if I can. There are plenty of designs where they do wonderful things to close timing, but if they're not needed please turn them off. That's usually a good starting point as to where the bulk of compile time is being spent.
When you say 30m-1hr with no changes and full incremental compile on, what are your partitions set to? Do you have physical synthesis turned on?