Special:Investigate has been around for a year and half. While there still exist some tasks from when implementation began, I would argue that calling the tool "new" isn't entirely true.
I propose that the link be removed and replaced with a subtitle link to Investigate, similarly to how Special:CheckUser is listed from Special:Investigate. While this does diminish how prominent the link is, this places the same level of importance in the page of the link to Special:CheckUser from Investigate. Also I don't think there will be a deprecation of Special:CheckUser as the Investigate tool does not provide all the actively used features in Special:CheckUser.
Instead, I propose that "new" be removed and a subtitle link to Investigate still be added to bring some consistency to the links.