I think that the travel times are fine. Bad roads do not allow quick movement.
It would be nice to be able to invest in roads between specific regions. That way you can choose to improve the roads you want improved without improving the ones you don't. If you know that you will be invading a neighbouring region, you could start improving the roads to that region, atleast halfway. This should NOT be a quick change, just quicker than it is now.
