Just been having this discussion with my brother and cousin. I posed the question, if you were in charge, what would you do with H5? Would you work out a way to bring Cortana back, or use the Chief's new-found characterisation, use the concept of him being "broken" and really have him go off the rails. The Chief has lost his best and only friend, and Cortana helping him discover his humanity (as opposed to being solely a soldier), it's going to hit him hard.
My brother gave my favourite response. Have Chief go off the rails in 5, perhaps engaged in a pursuit for an incarcerated Halsey (perhaps imprisoned by Covenant/Forerunner who understand just how important she is - who knows where Spartan Ops will take us...), in an attempt to not only save one of the most brilliant minds of the UNSC, but also to try and bring Cortana back. In 6, maybe we see the culmination of Chief and Halsey's efforts to bring her back.
I like the idea of her having flashes in the Chief's head, reminiscent of Halo 3. Easy to do, just say there are traces of her lingering in the tech he uses.
So yeah, the short story would be to have him go alone in 5, but trying to get her back. The final scene would have Halsey and Chief insert a chip into a console, which then shows a distorted, hazy image of blue and white, gradually focusing into Cortana's avatar lay down, eventually standing up and looking at them both, and then says ".....Chief?" *Curtain falls, cut to black, exit stage*
Replacing Cortana with another AI (without the intention of ever bringing Cortana back) would be sacrilege.