The occurrence of “Build options changed, rebuilding all” (as mentioned in edited question and shown in screen shot) probably is causing the large delay. My belief (correct or not) is that lots of libraries are being rebuilt when that message appears. Ordinarily, libraries should be rebuilt only upon initial install or when changing target board type.
An arduino.cc thread, “"Build options changed, rebuilding all" even when nothing changes ==> very slow”, from 2014 treats the issue superficially, merely pointing out that Arduino 1.5.8 Beta is suitable for Yún and Arduino Due boards, not “regular Arduino” boards.
A 2011 Google code thread probably is mostly irrelevant, but it's worth trying some steps mentioned in posts #14 and 15 ‒ eg, starting arduino via a path with no spaces in names ‒ if your platform is MS Windows. If the Arduino IDE cannot find its options or preference files it probably assumes it is starting from scratch.
Note, please edit the question to specify how you started the Arduino IDE running, where the IDE is installed on your system, what your op system is, and what your computer is.