Faits: A. Le 7 juin 2001, A._, ressortissant macédonien né en 1979, a épousé en Macédoine B._, ressortissante suisse née en 1978. Le 12 septembre 2001, il est entré en Suisse où il a obtenu une autorisation de séjour au titre de regroupement familial. Par requête du 25 octobre 2006, A._ a demandé la naturalisation facilitée qu'il a obtenue le 11 mars 2008, après avoir co-signé avec son épouse le 14 février 2008 une déclaration dans laquelle ils confirmaient vivre en communauté conjugale effective et stable. Le 6 juin 2008, les époux ont déposé une requête commune en divorce, assortie d'une convention sur les effets accessoires. Le divorce a été prononcé le 21 septembre 2008 et est devenu exécutoire le 12 janvier 2009. A._ s'est marié le 5 février 2009 avec une ressortissante macédonienne. Si une première grossesse s'est terminée par une fausse couche en 2008, deux enfants sont ensuite nés de cette union, respectivement en 2009 et en 2011. B. Le 20 mai 2009, l'Office fédéral des migrations (ODM) a indiqué à A._ qu'il lui appartenait d'examiner s'il y avait lieu d'annuler la naturalisation facilitée, au vu de son déménagement seul à Flamatt un mois après l'octroi de la naturalisation, du récent prononcé du divorce et de son remariage. Invité à se déterminé, l'intéressé a expliqué le 26 mai 2009, qu'au moment où les problèmes de couple étaient survenus, la procédure de naturalisation était "relativement terminée" et que la grossesse de son épouse actuelle - intervenue durant la période où le couple A._ et B._ avait décidé de "faire une pause" - avait accéléré la séparation. Son ex-femme a été entendue le 27 janvier 2011 en présence de A._. Elle a déclaré que ses obligations professionnelles étaient devenues plus importantes, péjorant ainsi leur vie de couple. Malgré leurs difficultés, elle envisageait encore à ce moment-là un avenir commun. Elle a relaté qu'au début de l'année 2008, son ex-époux était parti en vacances en Macédoine. Deux mois après son retour, il l'avait informée qu'il l'avait trompée durant son séjour et que la femme en question - sa future seconde épouse - était enceinte. Selon B._, cela avait été le "coup de grâce" pour leur couple. Elle a confirmé que la séparation de fait était intervenue en mai 2008 au moment où son époux avait déménagé à Flamatt. B._ a également souligné qu'au moment de la signature de la déclaration commune le 14 février 2008, elle n'avait pas encore eu connaissance de la relation extraconjugale que son ex-époux avait entretenue durant ses vacances au début de l'année 2008. A._ a formé des observations complémentaires le 21 juillet 2011, reconnaissant en particulier que préalablement à ses vacances au début de l'année 2008, il n'avait eu "peu ou pas de relations intimes" avec son ex-épouse et qu'à son retour en Suisse, il souhaitait continuer son mariage. La grossesse de son amie macédonienne avait cependant changé la situation. Après avoir obtenu l'assentiment des autorités cantonales, l'ODM a, par décision du 11 janvier 2012, prononcé l'annulation de la naturalisation. Relevant que les délais légaux de prescription avaient été respectés, l'office a retenu que l'enchaînement des faits - en particulier, la demande de naturalisation déposée le 2 novembre 2006, la relation extraconjugale durant le séjour en Macédoine au début de l'année 2008, l'octroi de la naturalisation le 11 mars 2008, la séparation de fait du couple en mai 2008, la requête commune de divorce déposée le 6 juin 2008, l'entrée en force du jugement de divorce le 12 janvier 2009 et le remariage le 5 février 2009 avec la jeune femme rencontrée durant les vacances susmentionnées - permettait d'établir que lors de la déclaration du 14 février 2008 ou au moment du prononcé de la naturalisation, le mariage de l'intéressé n'était pas constitutif d'une communauté conjugale effective et stable. La naturalisation facilitée avait donc été octroyée sur la base de déclarations mensongères, voire d'une dissimulation de faits essentiels. C. Le Tribunal administratif fédéral a rejeté le recours formé par A._ par arrêt du 30 août 2012. Relevant que l'ODM n'avait pas indiqué pour quelles raisons, il n'avait pas été exceptionnellement renoncé à étendre les effets de l'annulation de la naturalisation aux enfants de l'intéressé, l'autorité précédente a cependant considéré que le droit du recourant d'obtenir une décision suffisamment motivée avait été guéri pendant la procédure de recours. Elle a en outre estimé que le délai relatif de deux ans et celui péremptoire de huit ans imposés par la loi avaient été respectés. Elle a également jugé que l'enchaînement chronologique particulièrement rapide des faits et le laps de temps extrêmement court qui s'était écoulé entre l'octroi de la naturalisation facilitée et le dépôt de la demande commune de divorce étaient de nature à fonder la présomption de fait que la stabilité du mariage n'existait déjà plus, ni au moment de la déclaration commune, ni au moment de la décision de naturalisation. En particulier, les premiers juges ont souligné que la paternité ne pouvait être considérée comme un fait extraordinaire susceptible d'expliquer la détérioration du lien conjugal, puisque la liaison adultérine avait pris naissance au début de l'année 2008, alors que les époux avaient décidé de faire une pause et de fréquenter d'autres personnes. D. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler l'arrêt du Tribunal administratif fédéral et, subsidiairement, de lui renvoyer l'affaire pour nouvelle décision. Il se plaint d'une constatation inexacte des faits (art. 97 LTF) et d'une violation de l'art. 27 LN au motif que la relation adultérine serait intervenue après la signature de la déclaration commune du 14 février 2008. Invités à se déterminer, l'ODM a déposé des observations tandis que l'autorité précédente a renoncé à se déterminer. Par ordonnance du 8 novembre 2012, le Président de la Ire Cour de droit public du Tribunal fédéral a accordé l'effet suspensif.