I don’t believe this is a Steam issue, warm starts will generally be quicker and it depends how CK2 caches generated files ‐ it might be writing compiled shaders to disk that get erased on a reboot.
You can post on their forum http://forum.paradoxplaza.com/forum/forumdisplay.php?720-Paradox-Development-Studio
or contact customer service https://paradox.zendesk.com/home to find out if its an issue or standard behaviour.
It's not Steam Linux. CK2 takes an obscenely long time to launch in WINE, too.
Nothing extracted yet.
Each time CK2 is started for the first time it takes 1-3 minutes to go through all the splash screens. Surprisingly all next runs just take couple seconds. I guess the issue is that when Steam is started for the first time (since reboot) it creates cksum for all files of the game I want to play.