Sachverhalt:
A.
Die Staatsanwaltschaft des Kantons Basel-Stadt wirft X._ zusammengefasst vor, er habe am 13. Dezember 2000 zwischen ca. 01.35 Uhr und ca. 02.00 Uhr im Zuge einer heftigen Auseinandersetzung seine ehemalige Lebenspartnerin in deren Wohnung zunächst mit einer oder beiden Händen während verhältnismässig langer Zeit mit Tötungsvorsatz gewürgt und diese sodann, als er festgestellt habe, dass sie noch lebte, durch drei Schnitte an ihrer Halsvorderseite mit einem Dolch getötet.
B.
Das Strafgericht des Kantons Basel-Stadt verurteilte X._ am 23. Dezember 2016 wegen Mordes zu einer Freiheitsstrafe von 15 Jahren, unter Anrechnung der Auslieferungs-, Untersuchungs- und Sicherheitshaft seit dem 22. Mai 2015. Ferner entschied es über die Schadenersatz- und Genugtuungsforderungen der Privatkläger, verfügte über die beschlagnahmten Gegenstände und regelte die Kosten- sowie Entschädigungsfolgen.
C.
Auf Berufung von X._ und der Staatsanwaltschaft verurteilte das Appellationsgericht des Kantons Basel-Stadt X._ am 8. Juni 2018 wegen Mordes zu einer Freiheitsstrafe von 17 Jahren, unter Anrechnung der Auslieferungs-, Untersuchungs- und Sicherheitshaft seit dem 22. Mai 2015, entschied über die Schadenersatz- und Genugtuungsforderungen der Privatkläger und regelte die Kosten- sowie Entschädigungsfolgen.
D.
X._ beantragt mit Beschwerde in Strafsachen, (1.) das appellationsgerichtliche Urteil sei aufzuheben und er sei vollumfänglich freizusprechen. Eventualiter sei eine Strafe von fünf Jahren bei vorsätzlicher Tötung beziehungsweise zehn Jahren bei Annahme von Mord auszufällen. Subeventualiter sei das Verfahren an die Vorinstanz zur Neubeurteilung zurückzuweisen; (2.) in Aufhebung des angefochtenen Urteils sei die Auslieferungshaft ab 24. September 2014 anzurechnen; (3.) es seien keine Kosten zu erheben und es sei ihm eine angemessene Parteientschädigung zuzusprechen; (4.) ihm sei die unentgeltliche Rechtspflege und Verbeiständung zu gewähren.
E.
Die Staatsanwaltschaft und das Appellationsgericht des Kantons Basel-Stadt wurden zur Vernehmlassung, beschränkt auf die Strafzumessung und die Haftanrechnung, eingeladen. Beide beantragen die Abweisung der Beschwerde, wobei das Appellationsgericht auf die Einreichung einer Stellungnahme verzichtet. X._ replizierte.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt zunächst die vorinstanzliche Sachverhaltsfeststellung und Beweiswürdigung. Er macht geltend, es liege keine geschlossene Indizienkette vor. Erschwerend komme hinzu, dass nach dem Zeitablauf von 16 bis 18 Jahren, insbesondere bei einem Indizienprozess, praktisch keine Entlastungsbeweise geführt werden könnten, was die Vorinstanz nicht berücksichtige.
1.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Die vorinstanzliche Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG; vgl. auch Art. 105 Abs. 2 BGG). Offensichtlich unrichtig im Sinne von Art. 97 Abs. 1 BGG ist die Sachverhaltsfeststellung, wenn sie willkürlich ist (<ref-ruling> E. 2.3.1 S. 244; <ref-ruling> E. 2.2 S. 313; je mit Hinweis; vgl. zum Begriff der Willkür <ref-ruling> E. 2.3.1 S. 244; <ref-ruling> E. 4.1 S. 566; je mit Hinweisen). Die Rüge der Willkür muss in der Beschwerde explizit vorgebracht und substanziiert begründet werden (Art. 106 Abs. 2 BGG). Demzufolge genügt es nicht, einen von den tatsächlichen Feststellungen der Vorinstanz abweichenden Sachverhalt zu behaupten. Auf solche rein appellatorische Kritik am vorinstanzlich festgestellten Sachverhalt tritt das Bundesgericht nicht ein (<ref-ruling> E. 4.4 S. 354 f.; <ref-ruling> E. 2.4 S. 368; <ref-ruling> E. 6.3 S. 375).
Liegen keine direkten Beweise vor, ist nach der Rechtsprechung auch ein indirekter Beweis zulässig. Indizien sind Tatsachen, von denen auf das Vorliegen einer unmittelbar entscheiderheblichen Tatsache geschlossen werden kann. Eine Mehrzahl von Indizien, welche für sich allein betrachtet nur mit einer gewissen Wahrscheinlichkeit auf eine bestimmte Tatsache oder Täterschaft hindeuten und insofern Zweifel offen lassen, können in ihrer Gesamtheit ein Bild erzeugen, das den Schluss auf den vollen rechtsgenügenden Beweis von Tat oder Täter erlaubt. Würdigt das Gericht einzelne belastende Indizien willkürlich oder lässt es entlastende Umstände willkürlich ausser Acht, führt dies nicht zwingend zur Aufhebung des angefochtenen Urteils durch das Bundesgericht. Die Beschwerde ist nur gutzuheissen, wenn der Entscheid auch bei objektiver Würdigung des gesamten Beweisergebnisses offensichtlich unhaltbar und damit willkürlich ist. Der Beschwerdeführer, der vor Bundesgericht eine willkürliche Beweiswürdigung rügt, darf sich daher nicht darauf beschränken aufzuzeigen, wie einzelne Indizien willkürfrei zu würdigen gewesen wären (Urteile 6B_976/2017 vom 14. November 2018 E. 2.2; 6B_824/2016 vom 10. April 2017 E. 12.1 f. mit Hinweisen, nicht publ. in <ref-ruling>).
1.3. Die Vorinstanz prüft bei der Sachverhaltsermittlung sämtliche objektiven und subjektiven Beweismittel mit Blick darauf, ob sie eine Tatnähe des Beschwerdeführers begründen und inwiefern sich aus ihnen konkrete Indizien, die für oder gegen seine Täterschaft sprechen, herleiten lassen. Sie setzt sich zunächst mit den objektiven Beweismitteln auseinander. Diese betreffen in erster Linie das Kerngeschehen des angeklagten Sachverhalts, das heisst, die letzten Stunden vor der Tötung des Opfers, die Tat selbst und das Nachtatverhalten inklusive die angebliche Flucht des Beschwerdeführers. Danach prüft sie die subjektiven Beweismittel, die hauptsächlich das Verhältnis des Opfers zum Beschwerdeführer und die Umstände ihrer Beziehung beleuchten. In der Folge setzt sich die Vorinstanz mit den vom Beschwerdeführer vorgebrachten Einwänden gegen die erstinstanzliche Sachverhaltsfeststellung auseinander und misst diese an den objektiven und subjektiven Beweismitteln. Schliesslich legt sie den Sachverhalt fest, den sie als erstellt erachtet und ihrer rechtlichen Beurteilung zu Grunde legt (Urteil S. 14 ff.).
1.4.
1.4.1. Indem der Beschwerdeführer geltend macht, es liege "keine geschlossene Indizienkette" vor, und lediglich einzelne Glieder dieser "Kette" in Zweifel zu ziehen versucht, vermag er die Beweiswürdigung als Ganzes nicht in Frage zu stellen. Vielmehr müsste er sich mit der gesamten Beweislage befassen und darlegen, inwiefern aus seiner Sicht auch der aus der Gesamtheit der verschiedenen Indizien gezogene Schluss geradezu willkürlich ist (Urteile 6B_976/2017 vom 14. November 2018 E. 2.2; 6B_824/2016 vom 10. April 2017 E. 12.1 f. mit Hinweisen, nicht publ. in <ref-ruling>). Diesen Anforderungen genügt seine Beschwerde von vornherein nicht. Selbst wenn dies der Fall wäre, gelänge es dem Beschwerdeführer mit seinen Vorbringen nicht aufzuzeigen, dass die vorinstanzliche Beweiswürdigung schlechterdings unhaltbar ist.
1.4.2. Seine Ausführungen erschöpfen sich hinsichtlich der meisten von ihm thematisierten Punkte beziehungsweise Indizien in einer unzulässigen appellatorischen Kritik. Er beschränkt sich grösstenteils darauf, einige von der Vorinstanz als belastend gewerteten Indizien aufzugreifen und darzulegen, wie sie aus seiner Sicht zu werten sind, ohne sich mit der vorinstanzlichen Begründung auseinanderzusetzen. Dies ist beispielsweise der Fall, wenn er geltend macht, er habe sich nicht ins Ausland begeben, weil er auf der Flucht gewesen sei, sondern weil er erkannt habe, dass sein Asylantrag keine Chance habe, oder behauptet, es gebe keinerlei Beweise für seine Gewalttätigkeit gegenüber dem Opfer und die Vorinstanz habe die Familienstruktur sowie den Umstand nicht berücksichtigt, dass auch andere Täter in Frage kämen, oder schliesslich einwendet, er habe keinerlei Motiv für die Tat gehabt und sei sehr schockiert gewesen, als er vom Tod seiner früheren Freundin erfahren habe.
1.4.3. Unbegründet ist der Einwand hinsichtlich der vorinstanzlichen Würdigung des plötzlichen Abbruchs des telefonischen Kontakts zwischen Beschwerdeführer und Opfer. Während der Beschwerdeführer mit dem Opfer am Tag vor seinem Tod zwölfmal telefonierte, wurde unmittelbar nach dem Tod des Opfers und während des ganzen darauf folgenden Tages kein Anruf registriert. Diesen Umstand darf die Vorinstanz als Indiz für die Täterschaft des Beschwerdeführers werten (Urteil S. 21).
Ebenso wenig ist zu beanstanden, wenn die Vorinstanz die rund um den Todeszeitpunkt erfolgte 10-sekündige Telefonverbindung des Opfers mit dem Anschluss einer Person, die in den Umfeldabklärungen nirgends erschienen ist, weder als be- noch entlastend für den Beschwerdeführer wertet. Entgegen der Behauptung des Beschwerdeführers ist nicht erstellt, von wem der Anruf ausging und ob dieser angenommen oder auf eine Combox geleitet worden ist. Die Vorinstanz gelangt ohne Rechtsverletzung zum Schluss, die Hintergründe dieser Verbindung seien im Dunkeln geblieben, und berücksichtigt diese nicht weiter. Inwiefern die Vorinstanz daraus eine Belastung ableiten soll, führt der Beschwerdeführer nicht weiter aus (Urteil S. 22).
Er argumentiert weiter, die "Eskalation" mit dem neuen Freund des Opfers sei entgegen der Ansicht der Vorinstanz sehr belastend (wohl für den neuen Freund). Die Vorinstanz erwägt, auch das Verhältnis des Opfers mit seinem neuen Partner habe ein gewisses Konfliktpotential gehabt, aus welchem sich weitere Implikationen mit den jeweiligen Familien ergeben hätten. Sie zeigt in der Folge auf, dass zu Beginn der Strafuntersuchung Ermittlungen im gesamten Umfeld des Opfers getätigt worden seien und sich diese nicht nur auf den Beschwerdeführer beschränkt hätten. Zudem begründet sie nachvollziehbar, weshalb keine unzulässige Fokussierung vorliege und eine Täterschaft des neuen Freundes oder dessen Familienangehörigen nicht naheliege (Urteil S. 39 f.).
Was die Schnittführung beziehungsweise die Hand, mit der die Schnitte ausgeführt wurden, betrifft, kann vollumfänglich auf die willkürfreien Erwägungen der Vorinstanz verwiesen werden, zumal sich der Beschwerdeführer mit diesen nicht auseinandersetzt (Urteil S. 35 f.).
1.4.4. Die vorinstanzliche Sachverhaltsfeststellung ist gesamtheitlich betrachtet ausgewogen und nachvollziehbar. Sie lässt weder Willkür noch eine Verletzung des Grundsatzes "in dubio pro reo" erkennen. Insbesondere verlangt die Vorinstanz vom Beschwerdeführer nicht, dass er seine Unschuld beweist. Der Umstand, dass die gerichtliche Beurteilung erst 16 beziehungsweise 18 Jahre nach der Tat erfolgt, mag die Sachverhaltsfeststellung zwar erschweren, ist jedoch in der Flucht des Beschwerdeführers begründet und wirkt sich letztlich nicht zu dessen Nachteil aus. Die Beschwerde ist in diesem Punkt unbegründet.
2.
2.1. Der Beschwerdeführer kritisiert die rechtliche Würdigung seiner Tat als Mord. Entgegen der Ansicht der Vorinstanz deute die lange Auseinandersetzung gerade nicht auf Kaltblütigkeit hin. Er sei der vorsätzlichen Tötung schuldig zu sprechen.
2.2. Die Vorinstanz erwägt zusammenfassend, der Beschwerdeführer sei besonders hartnäckig vorgegangen, indem er zu mehreren Methoden gegriffen habe, um das Opfer zu töten. Selbst innerhalb der zweiten Phase habe er gleich drei Schnitte in den Hals seines Opfers gesetzt, was als weiteres Element auf seine Entschlossenheit hindeute. In Bezug auf die Skrupellosigkeit falle massgeblich ins Gewicht, dass das Opfer während der gesamten Zeit, in der es sich erfolglos gegen die von hinten erfolgende Umklammerung zur Wehr gesetzt habe, entsetzliche Todesängste habe ausstehen müssen. Das Erleben der Tötung müsse sich verschlimmert haben, als das Opfer realisiert habe, dass der Beschwerdeführer zu einem Dolch griff, und als es versucht habe, die Schnitte in seinen Hals abzuwehren. Das Opfer habe das Bewusstsein nicht sofort, sondern erst auf dem Teppich liegend nach wenigen Minuten verloren. Umgekehrt habe der Beschwerdeführer die Todesängste seines Opfers unmittelbar miterlebt. Er habe dessen Widerstand mit roher Gewalt gebrochen, ohne den Anblick des Opfers in seinem verzweifelten Todeskampf zum Anlass zu nehmen, das Vorhaben abzubrechen. Die solcherart konsequent und empathielos zu Ende gebrachte Vorgehensweise zeuge von einer ausgesprochen gefühlskalten und auf die Auslöschung eines Menschenlebens abzielenden Brutalität. Damit sei die Ausführung besonders skrupellos und die Tat als Mord zu qualifizieren.
In der Folge prüft die Vorinstanz die Motivlage des Beschwerdeführers, obschon sich diese ihrer Ansicht nach erst im Rahmen der Strafzumessung konkret niederschlage. Sie gelangt zum Schluss, in der Zeit vor der Tat hätten sich mehrere Faktoren realisiert, die dazu geführt hätten, dass sich das Opfer emotional vom Beschwerdeführer entfremdet habe, während er nicht mit dem Ende der Beziehung zurecht gekommen sei. Daraus erhelle, dass sich der Beschwerdeführer am Punkt angelangt gesehen habe, an welchem er sich die Unausweichlichkeit der Trennung habe eingestehen müssen. Dies sei die entscheidende Triebfeder für den Entschluss gewesen, seine frühere Freundin zu eliminieren. Dabei habe der Beschwerdeführer seinen durch die Zurückweisung verletzten Stolz, seine Eifer- und seine Rachsucht über das Selbstbestimmungsrecht seiner früheren Freundin gestellt. Dies mache die Beweggründe der Tat besonders verwerflich. Indem die Tötung dem Beschwerdeführer dazu gedient habe, seine eigenen, im Verhältnis zum Leben des Opfers niederrangigen Interessen durchzusetzen, habe er aus extremem Egoismus gehandelt. Damit habe er auch das Mordelement des besonders verwerflichen Beweggrunds erfüllt (Urteil S. 45 ff.).
2.3. Eine vorsätzliche Tötung ist als Mord zu qualifizieren, wenn der Täter besonders skrupellos handelt, namentlich wenn sein Beweggrund, der Zweck der Tat oder die Art der Ausführung besonders verwerflich sind (Art. 112 StGB). Mord zeichnet sich nach der Rechtsprechung durch eine aussergewöhnlich krasse Missachtung fremden Lebens bei der Durchsetzung eigener Absichten aus. Es geht um die besonders verwerfliche Auslöschung eines Menschenlebens. Für die Qualifikation verweist das Gesetz in nicht abschliessender Aufzählung auf äussere (Ausführung) und innere Merkmale (Beweggrund, Zweck). Diese müssen nicht alle erfüllt sein, um Mord anzunehmen. Entscheidend ist eine Gesamtwürdigung der äusseren und inneren Umstände der Tat. Die für eine Mordqualifikation konstitutiven Elemente sind jene der Tat selber, während Vorleben und Verhalten nach der Tat nur heranzuziehen sind, soweit sie tatbezogen sind (<ref-ruling> E. 4.1 S. 64 f.; <ref-ruling> E. 1a S. 13 f.; Urteile 6B_492/2018 vom 13. November 2018 E. 2.5.3; 6B_28/2017 vom 23. Januar 2018 E. 2.3; 6B_480/2016 vom 5. August 2016 E. 1.3.2; je mit Hinweisen). Die Art der Tatausführung ist besonders verwerflich, wenn sie unmenschlich oder aussergewöhnlich grausam ist beziehungsweise wenn dem Opfer mehr physische oder psychische Schmerzen, Leiden oder Qualen zugefügt werden, als sie mit einer Tötung notwendigerweise verbunden sind. Besonders verwerfliche Beweggründe liegen etwa vor, wenn mit der Tötung ohne ernsthaften Grund Rache geführt wird, beispielsweise wegen einer aufgelösten Liebesbeziehung (Urteil 6B_877/2014 vom 5. November 2015 E. 6.2 mit Hinweisen, nicht publ. in: <ref-ruling>).
2.4. Soweit die Vorinstanz ausführt, die Motivlage des Beschwerdeführers schlage sich erst im Rahmen der Strafzumessung konkret nieder, übersieht sie, dass für die Qualifikation einer Tat als Mord eine Gesamtwürdigung der äusseren und inneren Umstände der Tat vorzunehmen ist. Nach der Rechtsprechung kann eine besondere Skrupellosigkeit beispielsweise entfallen, wenn das Tatmotiv einfühlbar und nicht krass egoistisch war, so etwa wenn die Tat durch eine schwere Konfliktsituation ausgelöst wurde (<ref-ruling> E. 4.1 S. 65; <ref-ruling> E. 1a S. 14; Urteile 6B_492/2018 vom 13. November 2018 E. 2.5.3; 6B_28/2017 vom 23. Januar 2018 E. 2.3; je mit Hinweisen). Im Ergebnis verletzt die Vorinstanz jedoch kein Bundesrecht, wenn sie die Tat des Beschwerdeführers als Mord im Sinne von Art. 112 StGB qualifiziert. Dass der Beschwerdeführer vor seinem Eintreffen nicht geplant hatte, seine frühere Freundin umzubringen, schliesst nicht aus, dass er die Tat schliesslich kaltblütig beging. Die Vorinstanz hält zutreffend fest, dass der Beschwerdeführer bei der Tötung besonders hartnäckig und entschlossen vorging. Gemäss den verbindlichen vorinstanzlichen Feststellungen versuchte er zunächst, das Opfer zu erwürgen, wobei er mit aussergewöhnlicher Heftigkeit vorging. Obwohl sich das Opfer heftig zur Wehr setzte, so dass der Beschwerdeführer den Würgegriff mehrfach neu ansetzen musste, liess dieser nicht von ihm ab. Bereits dies zeugt von seiner Entschlossenheit. In der Folge versetzte der Beschwerdeführer dem Opfer von hinten drei Schnitte in den Halsbereich, wobei sich dieses weiterhin mit Leibeskräften wehrte und schrie, bis es seine Widerstandsfähigkeit einbüsste, zu Boden sank, das Bewusstsein verlor und schliesslich verstarb (Urteil S. 42 f., 45 f.). Der Beschwerdeführer liess sich auch vom verzweifelten Todeskampf des Opfers nicht beeindrucken. Sein unbeirrbares Vorgehen zeugt von einer erheblichen Gefühlskälte und Brutalität. Es ist nicht zu beanstanden, wenn die Vorinstanz sein Vorgehen als besonders skrupellos bewertet. Sein krass egoistischer Beweggrund, wozu sich der Beschwerdeführer im Übrigen vor Bundesgericht nicht äussert, vermag die besondere Skrupellosigkeit selbstredend nicht entfallen zu lassen. Die Beschwerde ist auch in diesem Punkt unbegründet.
3.
3.1. Der Beschwerdeführer wendet sich gegen die Strafzumessung. Er macht in erster Linie geltend, die Vorinstanz gehe fälschlicherweise davon aus, dass Art. 64 Abs. 5 aStGB nicht milder sei als Art. 48 lit. e StGB, und verweigere ihm zu Unrecht eine Strafmilderung infolge langen Zeitablaufs. Ferner hätte die Vorinstanz die Strafe angesichts des langen Zeitablaufs und seiner erhöhten Strafempfindlichkeit gestützt auf Art. 63 aStGB mindern müssen. Im Übrigen würden die vorinstanzlichen Ausführungen zur Strafzumessung den Begründungsanforderungen nicht genügen, da nicht nachvollziehbar sei, wie die Vorinstanz auf eine Freiheitsstrafe von 17 Jahren komme.
3.2. Die Vorinstanz widmet sich zunächst der objektiven Tatschwere und hält zusammengefasst fest, dass die Art der Tatausführung mit Blick auf die Verwerflichkeit im oberen Mittelfeld skrupellosen Handelns anzusiedeln sei. Das Verhalten des Beschwerdeführers sei mit Konsequenz auf die Tötung seiner früheren Freundin ausgerichtet gewesen und sei trotz ihres erbitterten Widerstands in der Art eines eigentlichen Todeskampfs bis zum Schluss durchgezogen worden. Das Miterleben der Grausamkeiten durch das Opfer hebe die Tat verschuldensmässig von denkbaren, weniger skrupellosen Tötungen deutlich ab. Die anhand des Tathergangs ermittelte objektive Tatschwere wiege mittel bis schwer. Hinsichtlich der subjektiven Tatschwere erwägt die Vorinstanz, dem Beschwerdeführer sei es mit der Tötung unterschwellig darum gegangen, seine frühere Freundin nicht aus seinem Leben, mithin seinem Einflussbereich, zu entlassen. Innerhalb der Spanne denkbarer verwerflicher Beweggründe, die für eine Rachetötung ausschlaggebend sein könnten, sei zu betonen, dass der Beschwerdeführer aufgrund seines übersteigerten Kontrollbedürfnisses und seiner Eifersucht selbst einen massgeblichen Anteil an der Eskalation des Konflikts gehabt habe. Daher wirke sich die Konfliktsituation nicht verschuldensmindernd aus. Zudem sei zu berücksichtigen, dass die Tat zwar nicht von langer Hand geplant gewesen sei, allerdings auch nicht mehr als spontane Überreaktion bezeichnet werden könne, nachdem der Beschwerdeführer das Opfer nach intensivem telefonischem Kontakt spät nachts in dessen Wohnung aufgesucht und die Tat anschliessend relativ zügig begangen habe. Dass der Beschwerdeführer seine früheren, unspezifischen Todesdrohungen gegenüber seiner ehemaligen Freundin später in die Tat umgesetzt habe, bekräftige, dass das Bestrafungselement bereits während längerer Zeit in seinem Bewusstsein vorhanden gewesen sei und bei der Motivbildung eine ausgeprägte Rolle gespielt habe. Zusammenfassend wiege auch das subjektive Tatverschulden unter der Berücksichtigung des Doppelverwertungsverbots mittel bis schwer. Angesichts sämtlicher objektiver und subjektiver Tatkomponenten sei das Verschulden insgesamt als mittel bis schwer zu bezeichnen und eine hypothetische tatbezogene Strafe von 17 Jahren festzusetzen.
In der Folge würdigt die Vorinstanz die Täterkomponenten und gelangt zum Schluss, dass sich diese strafneutral verhalten. Anschliessend prüft sie, ob die Strafe gestützt auf Art. 48 lit. e StGB infolge langen Zeitablaufs zu mildern ist. Dabei ermittelt sie vorab, welches Verjährungsrecht für den Beschwerdeführer das mildere ist und gelangt zum Schluss, dass die Verfolgungsverjährung sowohl nach altem wie auch nach neuem Recht am 13. Dezember 2030 eintrete, womit sich beide Regelungen hinsichtlich ihrer Strenge für den Beschwerdeführer als gleichwertig erwiesen. Folglich seien am 8. Juni 2018, am Tag der Eröffnung ihres Urteils, noch nicht zwei Drittel der Verjährungsfrist verstrichen gewesen, womit die Strafminderung im freien Ermessen des Gerichts liege. In Würdigung sämtlicher Umstände lasse sich keine Verminderung des Strafbedürfnisses erkennen, weshalb der Zeitablauf seit der Tat zu keiner Strafreduktion führe. Auch erkennt die Vorinstanz beim Beschwerdeführer keine erhöhte Strafempfindlichkeit.
Die Vorinstanz gelangt zum Schluss, der Beschwerdeführer sei in Würdigung sämtlicher relevanter Strafzumessungsfaktoren zu einer Freiheitsstrafe von 17 Jahren zu verurteilen (Urteil S. 52 ff.).
3.3. Der Beschwerdeführer hat die hier zu beurteilenden Straftaten vor Inkrafttreten des neuen Allgemeinen Teils des Strafgesetzbuches am 1. Januar 2007 (AS 2006 3459) begangen. Das angefochtene Urteil ist nach diesem Zeitpunkt ergangen. Gemäss Art. 2 Abs. 2 StGB gelangt bei dieser Konstellation das neue Recht zur Anwendung, sofern es für den Täter milder ist. Ob das neue im Vergleich zum alten Gesetz milder ist, beurteilt sich aufgrund eines konkreten Vergleichs der Strafe. Das Gericht hat zu prüfen, nach welchem der beiden Rechte der Täter besser wegkommt (<ref-ruling> E. 6.2.1 S. 87 f. mit Hinweisen). Freiheitsentziehende Strafen des früheren Rechts (Gefängnis oder Zuchthaus) und des neuen Rechts (Freiheitsstrafe) sind gleichwertig, soweit sie unbedingt ausgesprochen werden (a.a.O., E. 7.2.1 S. 89 f. mit Hinweisen).
Nach Art. 63 aStGB (AS 54 757) bemisst das Gericht die Strafe nach dem Verschulden des Täters zu. Er berücksichtigt die Beweggründe, das Vorleben und die persönlichen Verhältnisse des Schuldigen. Diese Bestimmung entspricht weitgehend der geltenden Regelung in Art. 47 StGB, und die früheren Strafzumessungsgrundsätze wurden in Art. 47 Abs. 1 StGB beibehalten. Die Bewertung des Verschuldens wird in Art. 47 Abs. 2 StGB dahingehend präzisiert, dass dieses nach der Schwere der Verletzung oder Gefährdung des betroffenen Rechtsguts, nach der Verwerflichkeit des Handelns, den Beweggründen und Zielen des Täters sowie danach bestimmt wird, wieweit der Täter nach den inneren und äusseren Umständen in der Lage war, die Gefährdung oder Verletzung zu vermeiden (<ref-ruling> E. 5.4 S. 59 mit Hinweis).
Gemäss Art. 48 lit. e StGB mildert das Gericht die Strafe, wenn das Strafbedürfnis in Anbetracht der verstrichenen Zeit deutlich vermindert ist und der Täter sich in dieser Zeit wohl verhalten hat. Dieser Strafmilderungsgrund entspricht inhaltlich im Wesentlichen dem Strafmilderungsgrund des Wohlverhaltens während verhältnismässig langer Zeit im Sinne von Art. 64 Abs. 5 aStGB (AS 54 757). Die diesbezügliche Rechtsprechung ist daher weiterhin zu beachten. Die verhältnismässig lange Zeit steht in Bezug zur Verjährungsfrist. Das Verjährungsrecht ist bereits durch das Bundesgesetz vom 5. Oktober 2001, in Kraft seit 1. Oktober 2002, revidiert worden (AS 2002 2993). Hinsichtlich der Verjährung verankert Art. 389 StGB beziehungsweise Art. 337 aStGB (AS 54 757) ausdrücklich die "lex mitior"-Regel. Das neue Verjährungsrecht unterscheidet nicht mehr zwischen relativen (ordentlichen) und absoluten Verjährungsfristen. Die neurechtlichen Verjährungsfristen entsprechen im Wesentlichen den altrechtlichen absoluten Fristen. Die Gegenstand des vorliegenden Verfahrens bildende Straftat des Mordes verjährte altrechtlich relativ in 20 und absolut in 30 Jahren (Art. 70 Abs. 1a StGB [AS 54 757] und Art. 72 Ziff. 2 Abs. 2 aStGB [AS 1951 1]). Neurechtlich verjährt sie in 30 Jahren (Art. 97 Abs. 1 lit. a StGB [AS 2013 4417 und AS 2006 3459] bzw. Art. 70 Abs. 1 lit. a aStGB [AS 2002 2993]).
Unter dem Geltungsbereich des alten Verjährungsrechts war der Strafmilderungsgrund des Wohlverhaltens während verhältnismässig langer Zeit gegeben, wenn die relative (ordentliche) Verjährung nahe war (<ref-ruling> E. Ic S. 203). Dies war nach der Rechtsprechung jedenfalls bei den allgemeinen Verjährungsfristen (<ref-ruling> E. 6.1.1 S. 2; <ref-ruling> E. Ib S. 202 f.) mit dem Ablauf von neun Zehnteln der relativen (ordentlichen) Verjährungsfrist anzunehmen (vgl. <ref-ruling> E. 6.2 S. 3 f.; <ref-ruling> E. Id S. 204; Urteile 6B_415/2010 vom 1. September 2010 E. 5.7; 6S.282/2005 vom 31. Januar 2007 E. 3.5; 6S.385/2001 vom 28. August 2001 E. 3c; 6S.238/1999 vom 4. Juni 1999 E. 7b) und galt auch für den Fall, dass die Verjährung inzwischen nach Art. 72 aStGB unterbrochen worden ist (<ref-ruling> E. Ic S. 203). Unter dem Geltungsbereich des seit 1. Oktober 2002 in Kraft stehenden neuen Verjährungsrechts (AS 2002 2993) ist dieser Strafmilderungsgrund nach der Rechtsprechung in jedem Fall anzunehmen, wenn mindestens zwei Drittel der Verjährungsfrist abgelaufen sind (<ref-ruling> E. 3.1 S. 148 mit Hinweisen). Für die Berechnung ist und war der Zeitpunkt des Sachurteils und damit vorliegend das Urteilsdatum des angefochtenen Entscheids massgebend (vgl. <ref-ruling> E. 3.1 S. 148; <ref-ruling> E. 6.2 S. 4; Urteil 6S.282/2005 vom 31. Januar 2007 E. 3.5). In welchem Mass die Strafe bei Vorliegen dieses Strafmilderungsgrunds zu reduzieren ist, hängt davon ab, wie viel Zeit zum massgebenden Zeitpunkt der Ausfällung des angefochtenen Urteils seit der Tat verstrichen ist (vgl. zum Ganzen: Urteil 6B_1065/2010 vom 31. März 2011 E. 1.9).
3.4. Indem die Vorinstanz bei der Strafzumessung (sowie bei der rechtlichen Würdigung) ohne weitere Prüfung das neue, geltende Recht anwendet, verkennt sie, dass dieses nur zur Anwendung gelangt, wenn es für den Täter das mildere ist (vgl. Art. 2 Abs. 2 StGB). Ob dies der Fall ist, beurteilt sich aufgrund eines konkreten Vergleichs der auszusprechenden Strafe (vgl. E. 3.3 hiervor); eine kombinierte Anwendung der beiden Rechte ist ausgeschlossen (<ref-ruling> E. 6.2.3 S. 88 mit Hinweisen). Soweit eine Freiheitsstrafe ausgesprochen wird, welche wie im vorliegend zu beurteilenden Fall den (teil-) bedingten Vollzug ausschliesst, erweist sich das neue Recht in der Regel nicht als milder. In diesem Fall gelangt das vor der Revision des Allgemeinen Teils des Strafgesetzbuchs geltende Recht zur Anwendung (vgl. Urteil 6B_446/2011 vom 27. Juli 2012 E. 5.4.1).
Das Verjährungsrecht wurde bereits vor dem (übrigen) Allgemeinen Teil des Strafgesetzbuchs revidiert. Diesbezüglich gelangt die Vorinstanz zum Schluss, die altrechtliche relative (ordentliche) Verjährungsfrist wäre bereits mehrfach unterbrochen worden, womit altrechtlich die absolute Verjährungsfrist von 30 Jahren zum Tragen käme. Da diese mit der neurechtlichen Verjährungsfrist übereinstimme, trete die Verfolgungsverjährung für den vorliegend zu beurteilenden Mord sowohl alt- als auch neurechtlich am 13. Dezember 2030 ein (Urteil S. 56). Diese Überlegungen der Vorinstanz treffen hinsichtlich des Eintritts der Verfolgungsverjährung zwar zu, übersehen jedoch, dass für die Beurteilung der Frage, ob die Strafe infolge Wohlverhaltens während langer Zeit zu mildern ist, nach der Rechtsprechung zum alten Verjährungsrecht nicht die absolute, sondern die relative (ordentliche) Verjährungsfrist von in casu 20 Jahren relevant ist (vgl. E. 3.3 hiervor). Weshalb von dieser Rechtsprechung abgewichen werden sollte, legt die Staatsanwaltschaft in ihrer Vernehmlassung nicht überzeugend dar, zumal sie - wie auch der Beschwerdeführer - fälschlicherweise davon auszugehen scheint, dass auch im Zusammenhang mit dem alten Verjährungsrecht die "zwei-Drittel-Regel" zur Anwendung gelangt (vgl. jedoch E. 3.3 hiervor; siehe zur Grundidee von Art. 64 Abs. 5 aStGB beziehungsweise Art. 48 lit. e StGB: <ref-ruling> E. 6.1 ff. S. 2 ff.).
Im konkreten Fall waren zum massgebenden Zeitpunkt der Ausfällung des angefochtenen Entscheids am 8. Juni 2018 seit der Tat vom 13. Dezember 2000 knapp 17 Jahre und 6 Monate verstrichen. Damit waren zwar noch nicht zwei Drittel der neurechtlichen Verjährungsfrist von 30 Jahren abgelaufen, jedoch beinahe neun Zehntel der altrechtlichen relativen (ordentlichen) Verjährungsfrist. Bei Anwendung des zum Zeitpunkt der Ausfällung des angefochtenen Urteils geltenden Verjährungsrechts wäre daher die Strafe nicht zu reduzieren. Jedenfalls ist nicht zu beanstanden, wenn die Vorinstanz zum Schluss gelangt, es lägen keine Besonderheiten vor, die es rechtfertigen könnten, den Strafmilderungsgrund des Wohlverhaltens während verhältnismässig langer Zeit schon bei Ablauf von weniger als zwei Drittel der Verjährungsfrist anzunehmen. Damit ist das neue Verjährungsrecht keinesfalls das mildere. Im Zeitpunkt der Ausfällung des angefochtenen Urteils war die relative (ordentliche) Verjährung nach Massgabe des alten Rechts bereits nahe. Es ist vorstellbar, dass daher bei Anwendung des alten Rechts die Strafe wegen des Wohlverhaltens während verhältnismässig langer Zeit reduziert würde. Da für die Beurteilung der Frage, ob und inwiefern die Strafe infolge Wohlverhaltens während langer Zeit zu mildern ist, neben dem Faktor Zeit weitere Umstände zu berücksichtigen sind (vgl. <ref-ruling> E. Ic S. 203 f.; Vernehmlassung der Staatsanwaltschaft Ziff. 1.4) und der Vorinstanz in diesem Zusammenhang ein gewisses Ermessen zusteht, ist es nicht am Bundesgericht, erstmals über diese Frage zu entscheiden.
Die Vorinstanz wird daher die Strafe in Anwendung des alten Verjährungsrechts und der hierzu ergangenen Rechtsprechung neu zumessen und begründen müssen. Es erübrigt sich daher grundsätzlich, auf die weiteren Rügen zur Strafzumessung einzugehen, insbesondere die Vorbringen des Beschwerdeführers, die Vorinstanz begründe die Höhe der Strafe nur unzureichend und sie hätte sein Wohlverhalten zumindest gestützt auf Art. 63 aStGB strafmindernd berücksichtigen müssen. Aus prozessökonomischen Gründen ist der Beschwerdeführer einzig auf die bundesgerichtliche Rechtsprechung hinzuweisen, wonach der Freiheitsentzug für jede beruflich sowie sozial integrierte Person eine Härte bewirkt und insoweit zu keiner Strafminderung führt; eine erhöhte Strafempfindlichkeit lässt sich nur bei aussergewöhnlichen Umständen bejahen (Urteile 6B_1416/2017 vom 29. November 2018 E. 1.4.4; 6B_698/2017 vom 13. Oktober 2017 E. 7.1.2; je mit Hinweisen).
4.
Hinsichtlich der Anrechnung der von ihm ausgestandenen Haft auf die ausgesprochene Freiheitsstrafe rügt der Beschwerdeführer, die Vorinstanz berücksichtige nicht, dass er am 26. August 2014 in Neuseeland verhaftet und am 24. September 2014 zwar gegen eine Kaution entlassen, jedoch bis zu seiner Auslieferung den strengen Regeln des Electronic Monitoring unterstanden habe.
Der Beschwerdeführer erhebt seine Rüge erstmals vor Bundesgericht, obwohl dies bereits zuvor möglich und zumutbar gewesen wäre. Bereits die Erstinstanz hat die Haft ab dem 22. Mai 2015 angerechnet. Mangels Ausschöpfung des kantonalen Instanzenzugs ist auf seine Rüge nicht einzutreten (vgl. Art. 80 Abs. 1 BGG; Urteile 6B_482/2018 vom 24. Januar 2018 E. 4.3; 6B_1101/2017 vom 30. Mai 2018 E. 1.8; je mit Hinweisen).
5.
Die Beschwerde ist teilweise gutzuheissen, das angefochtene Urteil aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Im Übrigen ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann.
Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren im Umfang seines Obsiegens zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Die Entschädigung ist praxisgemäss seinem Rechtsvertreter auszurichten. Insofern wird das Gesuch um unentgeltliche Rechtspflege und Verbeiständung gegenstandslos. Soweit der Beschwerdeführer mit seiner Beschwerde unterliegt, ist es zufolge Aussichtslosigkeit abzuweisen (Art. 64 Abs. 1 und 2 BGG). Seiner finanziellen Lage ist bei der Festsetzung der Gerichtskosten Rechnung zu tragen (Art. 65 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen, das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 8. Juni 2018 aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen, soweit es nicht gegenstandslos geworden ist.
3.
Dem Beschwerdeführer werden Gerichtskosten von Fr. 600.-- auferlegt.
4.
Der Kanton Basel-Stadt hat dem Vertreter des Beschwerdeführers, Advokat Dr. Stefan Suter, für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 1'500.-- auszurichten.
5.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Kammer, schriftlich mitgeteilt.
Lausanne, 26. Februar 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Andres