Faits: A. A.a. I._, ressortissante étrangère, est arrivée en Suisse en 1991 comme requérante d'asile. Sans formation professionnelle, elle a travaillé à compter du mois d'avril 2002 en qualité de nettoyeuse à des taux d'activité plus ou moins élevés. Souffrant depuis plusieurs années de problèmes psychiatriques (personnalité borderline), elle a déposé le 20 novembre 2003 une demande de prestations de l'assurance-invalidité. Quand bien même il estimait que l'atteinte psychique entraînait une incapacité totale de travailler, l'Office de l'assurance-invalidité du canton de Neuchâtel (ci-après: l'office AI) l'a rejetée, au motif que la condition d'assurance n'était pas remplie, l'assurée ne présentant pas, au moment de la survenance de l'invalidité en août 1994 (soit à l'échéance du délai de carence d'une année), au moins une année de cotisation (décision du 20 décembre 2004). A.b. En incapacité de travail totale depuis le 3 octobre 2009 en raison d'un eczéma des mains toxique-irritatif, I._ a présenté le 9 septembre 2010 une nouvelle demande de prestations de l'assurance-invalidité. Dans un avis médical du 10 octobre 2011 établi à l'intention de l'office AI, le Service médical régional de l'assurance-invalidité (SMR) a retenu l'existence d'une incapacité totale de travailler depuis le 1 er janvier 2010 en raison de problèmes psychiques et dermatologiques. Par décision du 25 janvier 2012, l'office AI a néanmoins rejeté la demande de prestations de l'assurée, au motif qu'elle présentait une incapacité de gain entière et ininterrompue depuis 1994, si bien qu'il n'y avait pas eu de nouveau cas d'assurance. B. Par jugement du 22 mars 2013, la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel a admis le recours formé par l'assurée, annulé la décision du 25 janvier 2012 et renvoyé la cause à l'office AI pour nouvelle décision au sens des considérants. C. L'office AI interjette un recours en matière de droit public contre ce jugement dont il demande en substance l'annulation.