Faits :
A.
A.a. Le 13 novembre 1995 au soir, B._, conseiller de la mission permanente de X._ auprès de l'Organisation des Nations-Unies (ONU), a été tué dans le sous-sol de l'immeuble où il était domicilié à Y._ de plusieurs balles tirées avec une arme de poing. Sur place, un dispositif réducteur de son (ci-après : silencieux) artisanal a été découvert; il était composé de mousse provenant d'un appuie-tête et de bande adhésive. Le jour suivant, le Ministère public de la Confédération (MPC) a ouvert une instruction contre inconnu pour meurtre, subsidiairement assassinat.
En 2007, quatre profils ADN, trois masculins et un féminin, ont été mis en évidence sur le silencieux.
Le 11 décembre 2009, le MPC a suspendu la procédure.
A.b. Selon de nouvelles analyses ADN, menées au printemps 2018, respectivement des recherches effectuées dans la base de données AFIS, une des traces laissées sur le silencieux appartenait à A._.
Le susmentionné a été arrêté le 30 octobre 2018 et placé en détention provisoire le 1er novembre suivant par le Tribunal des mesures de contrainte (Tmc) du canton de Berne pour une durée de trois mois.
A la suite de la requête du 24 janvier 2019 déposée par le MPC, le Tmc a, par ordonnance du 5 février 2019, prolongé cette mesure jusqu'au 29 avril 2019.
B.
Le 7 mars 2019, la Cour des plaintes du Tribunal pénal fédéral a rejeté le recours formé par A._ contre cette décision.
Cette autorité a considéré qu'il existait des soupçons suffisants de la commission d'infractions (cf. consid. 2.2.4 p. 5 ss), pouvant notamment être retenu le chef de prévention d'assassinat (cf. consid. 3.2.2 p. 10). Elle a ensuite relevé l'existence de risques de collusion (cf. consid. 2.3.2 p. 7 s.), ainsi que fuite (cf. consid. 2.4.2 p. 8 s.).
C.
Par acte du 27 mars 2019, A._ forme un recours en matière pénale contre cet arrêt, concluant à son annulation et au refus de la demande de prolongation de son placement en détention provisoire. Subsidiairement, il requiert le renvoi de la cause à l'autorité précédente pour nouvelle décision. Le recourant sollicite également l'octroi de l'assistance judiciaire.
Invitée à se déterminer, la Cour des plaintes a persisté dans les termes de sa décision, sans former d'observations. Quant au MPC, il a conclu au rejet du recours dans la mesure de sa recevabilité. Le 17 avril 2019, le recourant a persisté dans ses conclusions.

Considérant en droit :
1.
Selon l'art. 79 LTF, le recours en matière pénale est recevable contre les décisions de la Cour des plaintes du Tribunal pénal fédéral qui portent sur des mesures de contrainte, dont font partie les décisions relatives à la détention provisoire ou pour des motifs de sûreté au sens des art. 212 ss CPP (<ref-ruling> consid. 1.2 p. 87). Le recourant, prévenu actuellement détenu, a un intérêt juridique à la modification ou à l'annulation de la décision entreprise (art. 81 al. 1 let. a et b ch. 1 LTF). Le recours a été déposé en temps utile (art. 100 al. 1 LTF) et les conclusions qui y sont prises sont recevables (art. 107 al. 2 LTF). Partant, il y a lieu d'entrer en matière.
2.
Avec ses observations du 4 avril 2019, le MPC a produit différentes pièces - antérieures à l'arrêt attaqué et a priori faisant partie du dossier d'instruction - afin de répondre à certaines interrogations soulevées par le recourant dans son mémoire (cf. en particulier p. 6 de cette écriture). Vu l'issue du litige, la question de leur recevabilité - contestée par le recourant - peut cependant rester indécise.
Cela vaut d'autant plus qu'elles n'apparaissent pas déterminantes à ce stade de la procédure. En effet, la prescription de l'action pénale n'est pas invoquée par le recourant dans le cadre de la présente cause afin d'obtenir sa libération (cf. le courrier du 4 décembre 2018 y relatif). En outre, le rapport final de la police du 19 décembre 2007, produit en annexe de la demande de prolongation de la détention du 24 janvier 2019, suffit pour considérer en l'état que le silencieux a été utilisé; ainsi, ce rapport relève - certes avec renvoi aux deux rapports de police des 15 février et 20 mai 1996 joints aux déterminations du 4 avril 2019 - que "les deux derniers coups ont été tirés à une distance supérieure à 60 cm ou à travers le silencieux" (cf. p. 6). Quant au procès-verbal d'une audition du 15 août 2003, cette pièce tend uniquement à rappeler que l'enquête a permis d'établir qui était le propriétaire du sac plastique trouvé sur le lieu du crime - à savoir la victime -, thématique paraissant ainsi dénuée de toute pertinence; le recourant ne l'étaie d'ailleurs pas, se limitant à soulever une question.
3.
Le recourant ne remet pas en cause l'existence des risques de fuite et de collusion retenus par l'instance précédente. Il ne soutient pas non plus que des mesures de substitution permettraient de les pallier ou que la durée de la détention avant jugement subie violerait le principe de proportionnalité.
Si le recourant ne conteste pas l'existence de soupçons de la commissions d'infractions, il soutient en revanche que ceux-ci ne permettraient pas de retenir le chef de prévention d'assassinat (art. 112 CP), seule infraction dont l'action pénale ne serait pas prescrite à ce jour (cf. p. 7 du mémoire de recours).
3.1. Une mesure de détention provisoire ou pour des motifs de sûreté n'est compatible avec la liberté personnelle (art. 10 al. 2 Cst. et 5 CEDH) que si elle repose sur une base légale (art. 31 al. 1 et 36 al. 1 Cst.), soit en l'espèce l'art. 221 CPP. Elle doit en outre correspondre à un intérêt public et respecter le principe de la proportionnalité (art. 36 al. 2 et 3 Cst.). Pour que tel soit le cas, la privation de liberté doit être justifiée par un risque de fuite, un danger de collusion ou de réitération (cf. art. 221 al. 1 let. a, b et c CPP). Préalablement à ces conditions, il doit exister à l'égard de l'intéressé des charges suffisantes, soit de sérieux soupçons de culpabilité (art. 221 al. 1 CPP; art. 5 par. 1 let. c CEDH; <ref-ruling> consid. 2 p. 187 s.).
Selon la jurisprudence, il n'appartient pas au juge de la détention de procéder à une pesée complète des éléments à charge et à décharge et d'apprécier la crédibilité des personnes qui mettent en cause le prévenu. Il doit uniquement examiner s'il existe des indices sérieux de culpabilité justifiant une telle mesure. L'intensité des charges propres à motiver un maintien en détention préventive n'est pas la même aux divers stades de l'instruction pénale; si des soupçons, même encore peu précis, peuvent être suffisants dans les premiers temps de l'enquête, la perspective d'une condamnation doit apparaître avec une certaine vraisemblance après l'accomplissement des actes d'instruction envisageables (<ref-ruling> consid. 2.1 p. 333 s.; <ref-ruling> consid. 3.1 et 3.2 p. 318 s.).
En d'autres termes, les soupçons doivent se renforcer plus l'instruction avance et plus l'issue du jugement au fond approche. Si des raisons plausibles de soupçonner une personne d'avoir commis une infraction suffisent au début de l'enquête, ces motifs objectifs doivent passer de plausibles à vraisemblables (arrêt 1B_548/2018 du 8 janvier 2019 consid. 3.1).
3.2. L'assassinat (art. 112 CP) est une forme qualifiée d'homicide intentionnel qui se distingue du meurtre ordinaire (art. 111 CP) par le fait que l'auteur a tué avec une absence particulière de scrupules. Cela suppose une faute spécialement lourde et déduite exclusivement de la commission de l'acte; les antécédents ou le comportement que l'auteur adopte immédiatement après les faits n'entrent en ligne de compte que dans la mesure où ils y sont étroitement liés, et permettent de caractériser la personnalité de l'auteur (<ref-ruling> consid. 4.1 p. 64).
Pour caractériser la faute de l'assassin, l'art. 112 CP évoque le cas où les mobiles, le but ou la façon d'agir de l'auteur sont particulièrement odieux. Le mobile de l'auteur est notamment particulièrement odieux lorsqu'il tue pour obtenir une rémunération ou voler sa victime. Quant au but - qui se recoupe en grande partie avec le mobile -, il est particulièrement odieux lorsque l'auteur élimine un témoin gênant ou une personne qui l'entrave dans la commission d'une infraction. S'agissant de la façon d'agir, elle est particulièrement odieuse lorsqu'elle est barbare ou atroce ou lorsque l'auteur a exploité avec perfidie la confiance de la victime. L'énumération du texte légal n'est pas exhaustive. L'absence particulière de scrupules peut être admise lorsque d'autres éléments confèrent à l'acte une gravité spécifique. C'est ainsi que la réflexion et la planification de l'acte peuvent constituer des éléments susceptibles de conduire à retenir une absence particulière de scrupules. Par la froideur dans l'exécution et la maîtrise de soi, l'auteur manifeste également le plus complet mépris de la vie d'autrui (<ref-ruling> consid. 4.1 p. 64 s.).
Pour déterminer si l'on se trouve en présence d'un assassinat, il faut procéder à une appréciation d'ensemble des circonstances externes (comportement, manière d'agir de l'auteur) et internes de l'acte (mobile, but, etc.). Il y a assassinat lorsqu'il résulte de l'ensemble de ces circonstances que l'auteur a fait preuve du mépris le plus complet pour la vie d'autrui. Alors que le meurtrier agit pour des motifs plus ou moins compréhensibles, généralement dans une grave situation conflictuelle, l'assassin est une personne qui agit de sang-froid, sans scrupules, qui démontre un égoïsme primaire et odieux et qui, dans le but de poursuivre ses propres intérêts, ne tient aucun compte de la vie d'autrui. Chez l'assassin, l'égoïsme l'emporte en général sur toute autre considération. Il est souvent prêt, pour satisfaire des besoins égoïstes, à sacrifier un être humain dont il n'a pas eu à souffrir. La destruction de la vie d'autrui est toujours d'une gravité extrême. Pour retenir la qualification d'assassinat, il faut cependant que la faute de l'auteur, son caractère odieux, se distingue nettement de celle d'un meurtrier au sens de l'art. 111 CP (<ref-ruling> consid. 4.1 p. 65).
3.3. Après avoir confirmé l'existence de soupçons de la commission d'infractions, notamment eu égard aux preuves matérielles - analyses ADN et traces digitales - reliant le recourant au silencieux retrouvé sur le lieu du crime (cf. consid. 2.2.4 p. 5 ss), la Cour des plaintes a considéré que la fabrication d'un silencieux démontrait que l'homicide avait été réfléchi et planifié à l'avance. Elle a ensuite relevé que la situation financière du recourant à cette époque (cf. les procès-verbaux d'audition du 2 novembre 2018 [p. 4] et du 7 novembre 2018 [p. 8]), son passé violent (cf. le procès-verbal d'audition du 2 novembre 2018 [p. 5-11]), les précédentes infractions commises dans un but d'enrichissement (cf. le procès-verbal d'audition du 30 octobre 2018 [p. 5 s.]), ainsi que le statut diplomatique de la victime permettaient de penser que l'acte aurait pu être commis de la main du recourant en vue de percevoir une rémunération. Selon la juridiction précédente, il existait donc de forts indices tant pour l'infraction d'assassinat (art. 112 CP) que pour celle de meurtre (art. 111 CP; cf. consid. 3.2.2 p. 10).
3.4. Ce raisonnement ne prête pas le flanc à la critique. Si le recourant paraît contester les éléments retenus - qu'il a parfaitement identifiés (cf. p. 4 ss de son mémoire de recours) -, il ne développe cependant aucune argumentation propre à les remettre en cause.
En particulier, aucun élément - pris individuellement - ne permet de considérer que l'appréciation d'ensemble serait arbitraire (sur cette notion en lien avec l'appréciation des preuves, <ref-ruling> consid. 1.1 p. 503). Ainsi, un silencieux - sur lequel figurent par ailleurs l'ADN, ainsi que des traces digitales du recourant - peut effectivement démontrer une organisation de l'acte très grave prévu : les effets sonores liés à l'utilisation d'une arme à feu paraissent ainsi avoir été envisagés et des mesures pour y remédier - fabrication dudit objet - ensuite réalisées. Le recourant ne conteste pas avoir commis des infractions - notamment ultérieurement à 1995 - afin de s'enrichir. Il ne paraît ainsi pas exclu qu'un tel but puisse être également entré en considération antérieurement, notamment eu égard au défaut d'activité rémunératrice régulière qu'avait le recourant à la période des faits examinés (cf. les références précises données par l'autorité précédentes aux pages de ses auditions traitant de sa situation financière). Quant à son "passé violent", il prétend que les actes alors commis ne seraient pas de même nature ou n'auraient pas l'intensité ou les caractéristiques expliquant un assassinat. Ces comportements - qu'on ne saurait banaliser du fait qu'ils ont été principalement perpétrés contre ses compagnes - démontrent que le recourant n'hésite pas à avoir recours à la violence. Enfin, il n'invoque aucun élément de l'enquête - qui paraît se poursuivre activement (cf. les annexes mentionnées par le MPC à l'appui de sa requête de prolongation du 24 janvier 2019) - permettant d'envisager, même sous l'angle de la vraisemblance, que les charges retenues à son encontre - dont l'assassinat au sens de l'art. 112 CP - se seraient amoindries.
Dans le cadre de la détention avant jugement et à ce stade de la procédure, les éléments retenus par la Cour des plaintes - à qui il n'appartient pas de qualifier juridiquement définitivement les faits examinés - sont suffisants pour considérer, sans arbitraire, que le chef de prévention d'assassinat pourrait entrer en considération dans le cas d'espèce.
4.
Il s'ensuit que le recours est rejeté.
Le recourant a demandé l'octroi de l'assistance judiciaire (art. 64 al. 1 LTF). Les conditions y relatives étant réunies, il y a lieu d'admettre cette requête et de désigner Me Philippe Girod en tant qu'avocat d'office pour la procédure fédérale et de lui allouer une indemnité à titre d'honoraires, qui seront supportés par la caisse du Tribunal fédéral. Il n'est pas perçu de frais judiciaires (art. 66 al. 4 et 64 al. 1 LTF), ni alloué de dépens (art. 68 al. 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
La requête d'assistance judiciaire est admise. Me Philippe Girod est désigné comme avocat d'office du recourant et une indemnité de 1'500 fr. lui est allouée à titre d'honoraires, à payer par la caisse du Tribunal fédéral. Il n'est pas perçu de frais judiciaires.
3.
Le présent arrêt est communiqué au mandataire du recourant, au Ministère public de la Confédération et à la Cour des plaintes du Tribunal pénal fédéral.
Lausanne, le 23 avril 2019
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant : Merkli
La Greffière : Kropf