I think you need to get the Veteran Hall built. When that's done, click on 'Details' for your character and at the bottom, you should find the option 'retire' which gives you a NG+

Correction - I still think it's the Veteran Hall but you'll need to click on 'Company' in the menu and then scroll down until you find 'retire'.