Faits :
A.
A._, ressortissant algérien né en 1980, est entré en Suisse en vue d'épouser, le 24 mai 2005, une ressortissante suisse née en 1953, connue deux ans auparavant sur Internet.
Le 31 mai 2010, le prénommé a déposé une demande de naturalisation facilitée qu'il a obtenue le 8 février 2011, après avoir co-signé avec son épouse le 28 décembre 2010 une déclaration confirmant la stabilité et l'effectivité de leur communauté conjugale.
En avril 2012, A._ a annoncé son changement de domicile et s'est installé avec sa nouvelle compagne qui a donné naissance à leur enfant adultérin le 29 juillet 2013.
B.
Interrogée dans le cadre de la procédure en annulation de la naturalisation facilitée de A._, son épouse a notamment déclaré qu'il était possible que son époux ait rencontré sa nouvelle compagne en décembre 2011, étant donné que les problèmes de couple avaient commencé à cette époque; ceux-ci auraient consisté en des disputes et une "humeur maussade" de la part de l'intéressé. Après le décès en peu de temps des père et mère, ainsi que du frère aîné de son époux, celui-ci aurait consulté un psychologue qui lui aurait dit: "il vous faut divorcer". Son épouse a situé la date de la séparation du couple au début de l'année 2012 lorsque son époux aurait pris une chambre près de son lieu de travail. Elle a encore précisé qu'au moment de la naturalisation facilitée, en 2011, "ça allait très bien"; ils auraient d'ailleurs fêté cet événement en présence de sa mère et de son fils.
A._ a déclaré, par pli du 7 mars 2014, avoir connu sa nouvelle compagne, une collègue de travail, en décembre 2011. Les problèmes de couple seraient apparus en août 2011 et auraient été d'ordre financier. Il aurait en effet découvert en juillet 2011 que son épouse aurait eu des actes de défaut de biens pour 63'000 francs; il aurait alors consulté un psychologue, mais son épouse n'aurait été présente qu'à une seule séance. Le décès des trois membres de sa famille et la prise de connaissance des dettes de son épouse auraient conduit l'intéressé au burn-out; il aurait alors quitté le domicile conjugal.
Par décision du 16 juin 2014, l'Office fédéral des migrations (ODM; depuis le 1 er janvier 2015 le Secrétariat d'Etat aux migrations, SEM) a annulé la naturalisation facilitée de A._ et a précisé que cette annulation faisait également perdre la nationalité suisse aux membres de la famille du prénommé qui l'auraient acquise en vertu de la décision annulée.
C.
Le Tribunal administratif fédéral a confirmé cette décision dans un arrêt rendu le 15 septembre 2015. Il a considéré, en particulier, que l'enchaînement chronologique des événements fondait la présomption que la communauté conjugale formée par les intéressés n'était pas stable au moment de la signature de la déclaration commune et lors de la décision de naturalisation, et que les éléments avancés par l'intéressé n'étaient pas susceptibles de la renverser.
D.
A._ forme un recours en matière de droit public par lequel il conclut à l'annulation de l'arrêt du Tribunal administratif fédéral et au renvoi de la cause pour l'administration des moyens de preuves proposés; à défaut de renvoi, il conclut à l'annulation de la décision du SEM.
Invités à se déterminer, le SEM indique que le recours ne contient aucun élément susceptible de remettre en question l'arrêt entrepris, tandis que l'instance précédente renonce à formuler des observations.

Considérant en droit :
1.
Dirigé contre la décision du Tribunal administratif fédéral qui confirme l'annulation de la naturalisation facilitée accordée au recourant, le recours est recevable comme recours en matière de droit public (art. 82 al. 1 let. a et 86 al. 1 let. a LTF). Le motif d'exclusion de l'<ref-law> n'entre pas en ligne de compte, dès lors qu'il s'agit en l'espèce de naturalisation facilitée et non pas de naturalisation ordinaire. Pour le surplus, le recourant a qualité pour recourir au sens de l'<ref-law> et les conditions formelles de recevabilité sont remplies, de sorte qu'il y a lieu d'entrer en matière.
2.
Dans un premier moyen, le recourant se plaint d'une violation de son droit d'être entendu. Il fait grief à l'instance précédente d'avoir refusé de procéder à l'audition de son épouse ainsi que de la mère et du fils de cette dernière afin d'établir qu'au moment déterminant le couple était uni et stable. Il reproche également à l'autorité de ne pas avoir examiné et discuté les déclarations écrites des personnes précitées qu'il a produite en procédure.
2.1. Tel qu'il est garanti par l'art. 29 al. 2 Cst., le droit d'être entendu comprend notamment pour le justiciable le droit d'obtenir l'administration des preuves pertinentes et valablement offertes, de participer à l'administration des preuves essentielles et de se déterminer sur son résultat lorsque cela est de nature à influer sur la décision à rendre (cf. <ref-ruling> consid. 6.3.1 p. 299; <ref-ruling> consid. 3.2 p. 270; <ref-ruling> consid. 5.1 p. 293). Cette garantie constitutionnelle n'empêche pas l'autorité de mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude qu'elles ne pourraient l'amener à modifier son opinion (<ref-ruling> consid. 6.3.1 p. 299 et les réf. cit.; sur la notion d'arbitraire, cf. <ref-ruling> consid. 6.1 p. 205; <ref-ruling> consid. 5.1 p. 17). Il appartient au recourant de démontrer le caractère arbitraire par une argumentation répondant aux exigences de l'<ref-law>, respectivement de l'<ref-law> (<ref-ruling> consid. 4.1.2 p. 62).
2.2. En l'occurrence, l'instance précédente a estimé que les faits de la cause étaient suffisamment établis par les pièces figurant au dossier; elle a expliqué pour quelles raisons il n'y avait pas lieu de donner suite à la requête d'audition de témoins présentée par le recourant (son épouse ainsi que la mère et le fils de cette dernière). L'instance précédente, ayant procédé à l'examen anticipé des moyens de preuve demandés par le recourant, ce dernier devait démontrer, conformément aux exigences accrues de motivation rappelées ci-dessus, en quoi cette appréciation serait arbitraire. Or, le recourant se contente d'affirmer que l'instance précédente ne pouvait lui refuser l'administration de la contre-preuve et que ces moyens étaient de nature à établir qu'au moment déterminant le couple était uni et stable. Cette argumentation ne répond pas aux exigences accrues de motivation précitées, de sorte que sa critique est irrecevable. Le recourant se méprend en outre lorsqu'il affirme que l'instance précédente ne pouvait pas procéder à une appréciation anticipée des moyens de preuve.
Au demeurant, comme relevé par l'instance précédente, la procédure de recours régie par la PA est en principe écrite; selon l'<ref-law>, il n'est procédé à l'audition de témoins que si cette mesure paraît indispensable à l'établissement des faits de la cause. Or, le recourant a produit les déclarations écrites des témoins dont il a demandé l'audition. Il a ainsi été en mesure de verser au dossier tous les renseignements qu'il entendait fournir par lesdits témoins. Le recourant n'explique de plus pas ce que des commentaires oraux supplémentaires de ces personnes auraient apporté en plus dans la présente cause par rapport à leurs déclarations écrites; il ne démontre pas non plus en quoi des précisions supplémentaires de son épouse - qui a été entendue en janvier 2014 - seraient susceptibles de modifier l'appréciation de l'instance précédente. Enfin, il sied de relever qu'en considérant que les auditions de ces témoins n'étaient pas déterminantes en l'espèce, l'instance précédente a implicitement considéré qu'il en allait de même de leurs déclarations écrites censées attester que le couple ne connaissait pas de difficultés au moment de l'octroi de la naturalisation facilitée. Le grief tiré de la violation du droit d'être entendu doit donc être écarté.
3.
Le recourant se plaint ensuite d'une violation de l'art. 41 de la loi fédérale sur l'acquisition et la perte de la nationalité suisse du 29 septembre 1952 (LN; RS 141.0). Il invoque également une violation des art. 14 Cst. (droit au mariage et à la famille), 8 et 12 CEDH (droit au respect de la vie privée et familiale, et droit au mariage).
3.1. Conformément à l'art. 41 al. 1 LN, l'ODM peut, avec l'assentiment de l'autorité du canton d'origine, annuler la naturalisation ou la réintégration obtenue par des déclarations mensongères ou la dissimulation de faits essentiels.
3.1.1. Pour qu'une naturalisation facilitée soit annulée, il ne suffit pas qu'elle ait été accordée alors que l'une ou l'autre de ses conditions n'était pas remplie; il faut qu'elle ait été acquise grâce à un comportement déloyal et trompeur. S'il n'est point besoin que ce comportement soit constitutif d'une escroquerie au sens du droit pénal, il est nécessaire que l'intéressé ait donné sciemment de fausses informations à l'autorité ou qu'il l'ait délibérément laissée dans l'erreur sur des faits qu'il savait essentiels (<ref-ruling> consid. 2 p. 165; <ref-ruling> consid. 3.1 p. 115 et les arrêts cités). Tel est notamment le cas si le requérant déclare vivre en communauté stable avec son conjoint alors qu'il envisage de se séparer une fois obtenue la naturalisation facilitée; peu importe que son mariage se soit ou non déroulé jusqu'ici de manière harmonieuse (arrêts 1C_256/2012 du 22 novembre 2012 consid. 3.2.1; 1C_406/2009 du 28 octobre 2009 consid. 3.1.1 et l'arrêt cité).
La nature potestative de l'art. 41 al. 1 LN confère une certaine liberté d'appréciation à l'autorité compétente, qui doit toutefois s'abstenir de tout abus dans l'exercice de celle-ci. Commet un abus de son pouvoir d'appréciation l'autorité qui se fonde sur des critères inappropriés, ne tient pas compte de circonstances pertinentes ou rend une décision arbitraire, contraire au but de la loi ou au principe de la proportionnalité (<ref-ruling> consid. 3.1 p. 403; <ref-ruling> consid. 4a p. 101 et les arrêts cités).
D'après la jurisprudence, la notion de communauté conjugale suppose non seulement l'existence formelle d'un mariage, mais encore une véritable communauté de vie des conjoints; tel est le cas s'il existe une volonté commune et intacte de ceux-ci de maintenir une union conjugale stable; une séparation survenue peu après l'octroi de la naturalisation constitue un indice de l'absence de cette volonté lors de l'obtention de la citoyenneté suisse (<ref-ruling> consid. 2 p. 165; <ref-ruling> consid. 2 p. 484; <ref-ruling> consid. 3a p. 98).
3.1.2. La procédure administrative fédérale est régie par le principe de la libre appréciation des preuves (art. 40 de la loi fédérale de procédure civile fédérale du 4 décembre 1947 [PCF; RS 273], applicable par renvoi de l'<ref-law> [RS 172.021]). Ce principe vaut également devant le Tribunal administratif fédéral (<ref-law> [RS 173.32]). L'administration supporte le fardeau de la preuve lorsque la décision intervient, comme en l'espèce, au détriment de l'administré. Cela étant, la jurisprudence admet dans certaines circonstances que l'autorité puisse se fonder sur une présomption. C'est notamment le cas pour établir que le conjoint naturalisé a menti lorsqu'il a déclaré former une union stable, dans la mesure où il s'agit d'un fait psychique lié à des éléments relevant de la sphère intime, souvent inconnus de l'administration et difficiles à prouver (<ref-ruling> consid. 3 p. 166; <ref-ruling> consid. 3.2 p. 485). Partant, si l'enchaînement rapide des événements fonde la présomption de fait que la naturalisation a été obtenue frauduleusement, il incombe alors à l'administré de renverser cette présomption en raison, non seulement de son devoir de collaborer à l'établissement des faits (<ref-law>; cf. <ref-ruling> consid. 3 p. 166; <ref-ruling> consid. 3.2 p. 115 s.), mais encore de son propre intérêt (ATF <ref-ruling> consid. 3.2 p. 485 s.).
S'agissant d'une présomption de fait, qui ressortit à l'appréciation des preuves et ne modifie pas le fardeau de la preuve (cf. <ref-ruling> consid. 3 p. 166), l'administré n'a pas besoin, pour la renverser, de rapporter la preuve contraire du fait présumé, à savoir faire acquérir à l'autorité la certitude qu'il n'a pas menti; il suffit qu'il parvienne à faire admettre l'existence d'une possibilité raisonnable qu'il n'ait pas menti en déclarant former une communauté stable avec son conjoint. Il peut le faire en rendant vraisemblable, soit la survenance d'un événement extraordinaire susceptible d'expliquer une détérioration rapide du lien conjugal, soit l'absence de conscience de la gravité de ses problèmes de couple et, ainsi, l'existence d'une véritable volonté de maintenir une union stable avec son conjoint lorsqu'il a signé la déclaration (<ref-ruling> consid. 3 p. 165 s. et les arrêts cités).
3.2. En l'espèce, le Tribunal administratif fédéral a considéré que le court laps de temps séparant la déclaration commune (le 28 décembre 2010), l'octroi de la naturalisation facilitée (le 8 février 2011) et la déclaration de départ (13 avril 2012) était de nature à fonder la présomption que cette naturalisation a été acquise au moyen de déclarations mensongères, respectivement en dissimulant des faits essentiels. Ces éléments et leur chronologie, en particulier la séparation effective du couple intervenue environ une année après l'octroi de la naturalisation, permettent effectivement de fonder la présomption que celle-ci avait été obtenue frauduleusement (cf. arrêt 1C_796/2013 du 13 mars 2014 consid. 3.2). C'est en vain que le recourant conteste, par le biais des art. 14 Cst., 8 et 12 CEDH, ce mécanisme de présomption. Outre le fait que sa critique ne satisfait pas aux exigences accrues de motivation de l'<ref-law> s'agissant de la violation des droits fondamentaux, ce mécanisme a été maintes fois confirmé par la jurisprudence.
Par ailleurs, pour l'instance précédente, cette présomption était renforcée notamment par le fait que le recourant n'avait entrepris aucune procédure de mesure protectrice de l'union conjugale ou de tentative de conciliation et qu'il s'était rapidement accommodé de la rupture de son mariage: il avait ainsi entamé en décembre 2011 une nouvelle relation sentimentale - avec une femme de 38 ans plus jeune que son épouse - environ quatre mois après le début des difficultés dans son couple (qu'il a situé au plus tôt en août 2011) et avait quitté le domicile conjugal moins de cinq mois plus tard, soit en avril 2012, concevant un enfant adultérin avec sa nouvelle compagne seulement après quelques mois. L'instance précédente pouvait, sans violer le droit fédéral, prendre en compte ces éléments dans son appréciation.
Conformément à la jurisprudence précitée, il convient à présent d'examiner si le recourant est parvenu à renverser cette présomption en rendant vraisemblable, soit la survenance d'un événement extraordinaire susceptible d'expliquer une dégradation aussi rapide du lien conjugal, soit l'absence de conscience de la gravité des problèmes de couple au moment de la signature de la déclaration commune.
3.3. Le recourant se prévaut du fait que les époux ont tous deux affirmé que les difficultés du couple seraient survenues après la naturalisation vers la fin de l'année 2011. L'intéressé explique que l'origine de la séparation du couple résulterait de l'accumulation de plusieurs éléments (découverte des actes de défaut de biens de son épouse lorsqu'il aurait dû produire un extrait de ses poursuites pour un nouvel emploi; problèmes psychologiques et consultation d'un psychologue, etc.). Il invoque différents éléments qui établiraient la stabilité du couple au moment déterminant, tels la communication établie le 9 novembre 2010, les déclarations de son épouse et les attestations d'intimes du couple.
Les explications du recourant ne sont toutefois pas convaincantes et ne permettent pas de renverser la présomption établie. L'instance précédente pouvait en effet, sans violer le droit fédéral, considérer qu'il était peu probable que l'intéressé n'ait découvert la situation financière obérée de son épouse qu'après six ans de mariage, celle-ci percevant l'aide sociale et n'exerçant aucune activité lucrative depuis une longue période. Au demeurant, le fait de découvrir des actes de défaut de biens, même d'une certaine ampleur, n'est pas de nature à expliquer la fin subite de la vie d'un couple marié depuis de nombreuses années, sauf à considérer que leur union n'était pas stable. Il sied par ailleurs de relever que son épouse n'a jamais évoqué les problèmes financiers comme cause de la séparation.
Il apparaît en outre peu vraisemblable que les ex-époux, s'ils formaient réellement un couple effectif et stable, n'aient pas tenté d'une manière ou d'une autre de sauver leur union conjugale et qu'ils aient aussi rapidement accepté l'idée d'une séparation définitive; le recourant ayant de surcroît rapidement conçu un enfant avec sa nouvelle compagne. Il est donc peu plausible que le recourant n'ait découvert la dégradation de son couple qu'après l'obtention de la naturalisation facilitée. Il se prévaut à cet égard en vain du suivi psychologique entamé en décembre 2011. Comme relevé par l'instance précédente, ce suivi a commencé après le début de sa nouvelle relation amoureuse.
Enfin, les témoignages écrits de tiers et de membres de la famille de l'épouse du recourant - censés attester que le couple ne connaissait pas de difficultés conjugales - n'apparaissent pas décisifs et ne permettent pas de démontrer l'existence d'une communauté conjugale effective et stable tournée vers l'avenir, du point de vue des époux, lors de l'octroi de la naturalisation facilitée.
3.4. C'est ainsi sans violer le droit, en particulier l'art. 41 LN, que le Tribunal administratif fédéral a confirmé l'annulation de la naturalisation facilitée octroyée au recourant.
4.
Il s'ensuit que le recours est rejeté dans la mesure de sa recevabilité. Le recourant qui succombe supporte les frais de la présente procédure (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué au mandataire du recourant, au Secrétariat d'Etat aux migrations et au Tribunal administratif fédéral, Cour III.
Lausanne, le 25 février 2016
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Fonjallaz
La Greffière : Arn