Sachverhalt:
A.
Das Appellationsgericht des Kantons Basel-Stadt verurteilte A._ am 8. Juni 2018 wegen Mordes an seiner ehemaligen Lebenspartnerin, begangen am 13. Dezember 2000. Es bestrafte ihn mit einer Freiheitsstrafe von 17 Jahren.
B.
Das Bundesgericht hiess die Beschwerde gegen dieses Urteil betreffend die Strafzumessung gut und wies die Sache zur neuen Beurteilung an das Appellationsgericht zurück, damit dieses die Strafe in Anwendung des alten Verjährungsrechts und der hierzu ergangenen Rechtsprechung neu zumesse und begründe. Im Übrigen wies es die Beschwerde ab, soweit es darauf eintrat (Urteil 6B_1053/2018 vom 26. Februar 2019).
C.
Am 23. Oktober 2019 verurteilte das Appellationsgericht des Kantons Basel-Stadt A._ wegen Mordes zu einer Freiheitsstrafe von 16 Jahren und sechs Monaten.
D.
A._ führt Beschwerde in Strafsachen. Er beantragt, das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 23. Oktober 2019 sei aufzuheben und er sei mit einer Freiheitsstrafe von 10 Jahren zu bestrafen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Gleichzeitig ersucht er um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt, die vorinstanzliche Strafzumessung verletze Art. 64 und Art. 65 aStGB. Die Strafmilderung sei zu tief ausgefallen und es fehle eine Begründung, weshalb die Vorinstanz die Strafe lediglich um sechs Monate reduziere. Die Strafmilderung bemesse sich am gesamten Zeitablauf seit der Tat, und nicht bloss am Zeitablauf seit Verstreichen von 9/10 der Verjährungsfrist. Dabei berechne die Vorinstanz die verstrichene Frist falsch. Seit der Tat seien nicht bloss 9/10, sondern 19/20 der Verjährungsfrist abgelaufen.
1.2. Die Vorinstanz erwägt im angefochtenen Urteil vom 23. Oktober 2019, der Beschwerdeführer habe seine Ex-Freundin in den frühen Morgenstunden des 13. Dezember 2000 in deren Wohnung aufgesucht und nach einer heftigen Auseinandersetzung getötet. Zur Begründung ihrer Strafzumessung (noch ohne Strafmilderung zufolge Zeitablaufs) verweist die Vorinstanz auf ihr Urteil vom 8. Juni 2018, in welchem sie 17 Jahre Freiheitsstrafe als der Tat und Schuld des Beschwerdeführers angemessen erachtet hat.
Im Urteil vom 8. Juni 2018 ging die Vorinstanz von einem mittleren bis schweren objektiven Tatverschulden aus. Der Beschwerdeführer habe die Tötung trotz des erbitterten Widerstandes und des Todeskampfes seiner Ex-Freundin vollendet. Verschuldenserhöhend falle ins Gewicht, dass er das Opfer zuerst mit blossen Händen habe "erledigen" wollen. Erst als sich der Versuch als untauglich erwiesen habe, habe er dem Opfer mit einem Dolch mehrfach in die Kehle geschnitten. Dieses habe das Bewusstsein erst nach einigen Minuten verloren und diese Zeit widerstandsunfähig am Boden liegend miterlebt. Währenddessen habe sich der Beschwerdeführer in die Küche begeben und die Tatwaffe in einer Plastiktasche verstaut. Anschliessend habe er den Tatort verlassen, ohne sich mit dem im Sterben begriffenen Opfer zu beschäftigen. Zu den subjektiven Tatkomponenten erwog die Vorinstanz, der Auslöser für die Bluttat sei die Beendigung der Liebesbeziehung durch das Opfer und dessen Heiratsabsichten mit einem anderen Mann gewesen. Der Beschwerdeführer sei gekränkt gewesen und habe das Opfer auch nach der Trennung nicht aus seinem Einflussbereich entlassen wollen. Zwar sei die Tat nicht von langer Hand geplant gewesen, allerdings könne sie auch nicht als spontane Überreaktion bezeichnet werden, denn der Beschwerdeführer habe das Opfer nach intensivem telefonischen Kontakt spät nachts in dessen Wohnung aufgesucht und die Tat anschliessend relativ zügig begangen. Erschwerend falle ins Gewicht, dass der Beschwerdeführer dem Opfer die Tat bereits bei diversen Auseinandersetzungen angekündigt und mit bestialischen Schilderungen untermalt habe. Die Bestrafung habe beim Tatmotiv eine Rolle gespielt. Zusammenfassend sei das subjektive Tatverschulden als mittel bis schwer zu gewichten. Angesichts des objektiven und subjektiven Tatverschuldens erachtete die Vorinstanz eine Freiheitsstrafe von 17 Jahren als angemessen.
In Bezug auf die Täterkomponenten berücksichtigte die Vorinstanz im Urteil vom 8. Juni 2018, dass der Beschwerdeführer 1990 aus Sri Lanka in die Schweiz eingereist ist. Sein Asylgesuch sei am 13. Dezember 2000 abgelehnt worden, wobei ihm der Entscheid aufgrund seiner Flucht nach der Bluttat nicht mehr eröffnet worden sei. Während seines Aufenthaltes in der Schweiz habe der Beschwerdeführer im Raum Basel gelebt und verschiedene Hilfstätigkeiten in der Gastronomie ausgeübt. Obschon es im Rahmen der Beziehung zum Opfer wiederholt zu tätlichen Auseinandersetzungen gekommen sei, würden die Strafregisterauszüge keine Einträge aufweisen. Entsprechend sei die Vorstrafenlosigkeit neutral zu gewichten. Nach der Tat habe der Beschwerdeführer die Schweiz fluchtartig verlassen. Seine ungeplanten Selbstbegünstigungshandlungen (z.B. der Wechsel des Fahrzeugs oder das Waschen blutiger Kleidung) würden sich neutral auswirken. Hingegen zeuge es von einer gewissen Abgebrühtheit, dass der Beschwerdeführer nach der Tat ein neues Leben begonnen, geheiratet, eine Familie gegründet und während Jahren als unbescholtener Bürger in Neuseeland gelebt habe, wie wenn nichts geschehen wäre. Es könne ihm jedoch nicht zum Vorhalt gemacht werden, dass er aufgrund seiner unauffälligen Lebensführung erst nach über zehn Jahren habe aufgespürt werden können. Insgesamt wirke sich das Nachtatverhalten neutral auf die Strafzumessung aus. Während des Strafverfahrens habe der Beschwerdeführer mit Ausnahme der Berufungsverhandlung die Aussage verweigert, die Anklage bestritten und damit weder Einsicht noch Reue gezeigt. Dieses Verhalten wirke sich auf die Strafzumessung ebenfalls neutral aus. Im Haftalltag verhalte sich der Beschwerdeführer tadellos. Zusammenfassend seien die Täterkomponenten neutral zu gewichten.
Ergänzend zum Urteil vom 8. Juni 2018 erwägt die Vorinstanz im angefochtenen Urteil, massgebend für die Strafmilderung zufolge Zeitablaufs sei, dass bis zum erneuten Urteil vom 23. Oktober 2019 knapp neunzehn Jahre seit der Tat verstrichen seien. Dies entspreche mehr als 9/10 der relativen (ordentlichen) Verjährungsfrist. Die objektive Nähe der Verjährung sei erreicht, so dass eine Strafmilderung nach Art. 64 aStGB in Betracht falle. Eine solche Strafmilderung rechtfertige sich allerdings erst seit weniger als einem Jahr. Der Eintritt der absoluten Verfolgungsverjährung liege noch über elf Jahre entfernt. Der Beschwerdeführer habe sich seit der Tat nichts mehr zu Schulden kommen lassen, weder in Neuseeland noch in der Schweiz. Er sei seit dem 22. Mai 2015 in Haft, weshalb sich sein Wohlverhalten in Freiheit auf weniger als 14.5 Jahre beschränke. Dies entspreche gut 3/4 der massgeblichen Frist von 18 Jahren, welche die Strafmilderung überhaupt erst zur Anwendung kommen lasse. Zwar sei dem Berufungskläger zugutezuhalten, dass er sich auch im Strafvollzug angepasst gezeigt und insofern wohl verhalten habe. Dennoch falle diese Zeit aufgrund der eingeschränkten Möglichkeiten zur Persönlichkeitsentfaltung weniger stark ins Gewicht, als dieselbe Dauer der Bewährung in Freiheit. Angesichts dieser Umstände rechtfertige sich bloss eine Strafminderung im untersten Bereich, d.h. um sechs Monate. Die Freiheitsstrafe sei damit auf insgesamt 16 Jahre und sechs Monate festzulegen.
1.3.
1.3.1. Die abstrakte Strafdrohung für Mord nach Art. 112 aStGB beträgt lebenslängliches Zuchthaus oder Zuchthaus nicht unter zehn Jahren.
1.3.2. Nach Art. 63 aStGB misst das Gericht die Strafe nach dem Verschulden des Täters zu. Es berücksichtigt die Beweggründe, das Vorleben und die persönlichen Verhältnisse des Schuldigen. Diese Bestimmung entspricht weitgehend der geltenden Regelung in <ref-law>. Die Bewertung des Verschuldens wird in <ref-law> 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). Das Bundesgericht hat die Grundsätze der Strafzumessung nach Art. 63 aStGB bzw. <ref-law> wiederholt dargelegt (<ref-ruling> E. 6.1 S. 66 ff.; <ref-ruling> E. 5.4 ff. S. 59 ff.; je mit Hinweisen). Darauf kann verwiesen werden.
1.3.3. In dem für die Vorinstanz verbindlichen Rückweisungsentscheid (Urteil 6B_1053/2018 vom 26. Februar 2019 E. 3.4) hat das Bundesgericht entschieden, dass für die Frage der Strafmilderung zufolge Zeitablaufs das alte Verjährungsrecht und die dazu ergangene Rechtsprechung massgebend sei. Im Zeitpunkt des Entscheides der Vorinstanz vom 8. Juni 2018 seien nahezu 9/10 der altrechtlichen relativen (ordentlichen) Verjährungsfrist von 20 Jahren abgelaufen, weshalb geprüft werden müsse, ob die Strafe wegen Wohlverhaltens während langer Zeit zu reduzieren sei.
Gemäss Art. 64 aStGB kann der Richter die Strafe mildern, wenn seit der Tat verhältnismässig lange Zeit verstrichen ist und der Täter sich während dieser Zeit wohl verhalten hat. Der heilende Einfluss der Zeit, der in den Fristen des Art. 70 aStGB zur Verjährung führt, soll in den Fällen, bei denen die Verjährungsfrist nahezu abgelaufen ist, die Strafmilderung ermöglichen, wenn sich der Täter in dieser Zeit wohl verhalten hat. Neigt sich die ordentliche Verjährungsfrist ihrem Ende zu und ist dem Täter bis dahin nichts Nachteiliges mehr vorzuwerfen, so soll die Strafe gemildert werden können, auch wenn die Verjährung inzwischen nach Art. 72 aStGB unterbrochen worden ist (<ref-ruling> E. Ic S. 203). Hat der Täter durch sein eigenes Verhalten das Verfahren verlängert und damit Unterbrechungen herbeigeführt oder hat er sich nachträglich, seit Ablauf der ordentlichen Verjährungsfrist, nicht wohl verhalten, so kann dem beim Entscheid über die Strafmilderung immer noch Rechnung getragen werden. Denn auch wenn an sich eine der Voraussetzungen von Art. 64 aStGB zutrifft, so ist der Richter nicht schon verpflichtet, von der Strafmilderung Gebrauch zu machen. Vielmehr hat er nach seinem Ermessen darüber zu entscheiden, ob die gesamten Umstände eine solche rechtfertigen (<ref-ruling> E. Ic S. 203 f. mit Hinweisen).
Findet der Richter, die Strafe sei zu mildern, so erkennt er statt auf lebenslängliches Zuchthaus auf Zuchthaus von mindestens zehn Jahren (Art. 65 Abs. 1 aStGB) bzw. statt auf Zuchthaus mit besonders bestimmter Mindestdauer auf Zuchthaus (Art. 65 Abs. 2 aStGB), d.h. auf Zuchthaus von mindestens einem Jahr (siehe Art. 35 aStGB). Ist ein Strafmilderungsgrund nach Art. 64 aStGB gegeben, so hat dies entgegen dem Wortlaut von Art. 65 aStGB indessen nicht zur Folge, dass anstelle der Strafdrohung der anzuwendenden Strafbestimmung jene von Art. 65 aStGB tritt. Art. 65 aStGB bewirkt nach seinem Sinn und Zweck lediglich eine Erweiterung des ordentlichen Strafrahmens nach unten. Eine Verpflichtung zur Unterschreitung des ordentlichen Strafrahmens besteht jedoch nicht (<ref-ruling> E. 2 S. 12 ff.).
1.3.4. Dem Sachgericht steht bei der Gewichtung der verschiedenen Strafzumessungsfaktoren ein erheblicher Ermessensspielraum zu. Das Bundesgericht greift auf Beschwerde hin nur in die Strafzumessung ein, wenn die Vorinstanz den gesetzlichen Strafrahmen über- oder unterschritten hat, wenn sie von rechtlich nicht massgebenden Kriterien ausgegangen ist oder wesentliche Gesichtspunkte ausser Acht gelassen beziehungsweise in Überschreitung oder Missbrauch ihres Ermessens falsch gewichtet hat (<ref-ruling> E. 1.2 S. 319; <ref-ruling> E. 5.6 S. 61 mit Hinweis). Eine Beschwerde ist nicht alleine deshalb gutzuheissen, um die Begründung zu verbessern oder zu vervollständigen, soweit die Entscheidung im Ergebnis bundesrechtskonform erscheint (<ref-ruling> E. 2c S. 104 f.; mit Hinweisen).
1.4.
1.4.1. Die vom Beschwerdeführer beanstandete Strafzumessung erweist sich als bundesrechtskonform. Es ist nicht ersichtlich, dass die Vorinstanz sich von sachfremden Kriterien hätte leiten lassen oder das ihr zustehende Ermessen überschritten hätte. Aus der Begründung des angefochtenen Entscheids ergibt sich, auf welche Überlegungen die Vorinstanz ihren Entscheid stützt. Eine Verletzung der Begründungspflicht ist nicht auszumachen
1.4.2. Art. 64 und Art. 65 aStGB gewähren keinen Anspruch auf eine bestimmte Höhe der Strafreduktion infolge Zeitablaufs. Erachtet der Richter eine solche Reduktion als angezeigt, so ist diese nicht linear, anhand der verstrichenen Verjährungsfrist zu bemessen und sie folgt keiner starren mathematischen Regel. Soweit der Beschwerdeführer geltend macht, die Vorinstanz berechne die abgelaufene Verjährungsfrist falsch und es seien 19/20 und nicht bloss 9/10 (entsprechend 18/20) der relativen Verjährungsfrist abgelaufen, geht seine Argumentation fehl. Denn aus der vom Beschwerdeführer geltend gemachten geringfügigen Differenz folgt nicht zwingend eine höhere Strafreduktion. Im Übrigen geht auch die Vorinstanz davon aus, es seien "mehr als 9/10" der Verjährungsfrist, und nicht bloss "exakt 9/10", abgelaufen.
1.4.3. Die Vorinstanz berücksichtigt in vertretbarer Weise, dass der Zeitpunkt, seit welchem die Strafreduktion zufolge Zeitablaufs in Betracht fällt, erst vor Kurzem eingetreten ist. Weiter trägt sie dem Umstand Rechnung, dass sich das Wohlverhalten des Beschwerdeführers in Freiheit auf weniger als 14,5 Jahre beschränke und dessen Wohlverhalten in Haft weniger Gewicht zuzumessen sei, als einer Bewährung in Freiheit. Dass die Vorinstanz unter den gegebenen Umständen des vorliegend zu beurteilenden Falles eine geringe Reduktion der Strafe von einem halben Jahr als angemessen erachtet, stellt keinen Ermessensmissbrauch dar, auch wenn die Reduktion auf den ersten Blick gering erscheinen mag. So ist in diesem Zusammenhang insbesondere zu beachten, dass die späte Durchführung des Strafverfahrens und die Nähe der Verjährung darauf zurückzuführen sind, dass der Beschwerdeführer unmittelbar nach der Tat ins Ausland flüchtete und erst im Jahre 2011 ausfindig gemacht werden konnte. Die lange Zeitdauer seit Begehung der Tat ist damit weitgehend vom Beschwerdeführer zu verantworten. Dieser Umstand darf im Entscheid über die Strafmilderung durchaus berücksichtigt werden (vgl. E. 1.3.3 hiervor) und führt vorliegend auch nicht zu einer unzulässigen Doppelverwertung, zumal dem durch den Beschwerdeführer zu vertretenden Zeitablauf seit Begehung der Tat, für die Begründung des Verschuldens keine ausschlaggebende Bedeutung beigemessen wurde. Unter diesen konkreten Umständen liegt die Reduktion der Strafe um ein halbes Jahr jedenfalls noch im sachrichterlichen Ermessen und die ausgefällte Freiheitsstrafe von 16 Jahren und 6 Monaten ist im Ergebnis bundesrechtlich nicht zu beanstanden.
2.
Die Beschwerde ist abzuweisen. Der Beschwerdeführer wird ausgangsgemäss kostenpflichtig (<ref-law>). Sein Gesuch um unentgeltliche Rechtspflege ist in Anwendung von <ref-law> wegen Aussichtslosigkeit abzuweisen. Der finanziellen Lage des Beschwerdeführers ist mit reduzierten Gerichtskosten Rechnung zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'200.- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Kammer, schriftlich mitgeteilt.
Lausanne, 19. Februar 2020
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Rohrer