Faits:
A.
Par jugement du 24 mai 2012, le Tribunal d'application des peines et des mesures du canton de Genève a prononcé l'exequatur de l'arrêt rendu le 25 mai 2010 par la Cour d'appel de Durrës/Albanie reconnaissant X._ coupable d'"escroquerie ayant entraîné de graves conséquences" (art. 143 du code pénal albanais) et le condamnant à une peine privative de liberté de sept ans, avec la précision que l'exequatur était prononcée à concurrence de cinq ans.
B.
Par arrêt du 7 novembre 2012, la Chambre pénale d'appel et de révision de la Cour de justice genevoise a rejeté l'appel formé par X._, ajoutant que la peine subie avant jugement sera déduite de la peine à exécuter.
C.
X._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt, concluant, sous suite de dépens, principalement à sa réforme en ce sens que l'exequatur est rejetée, subsidiairement à son annulation. Il sollicite par ailleurs l'effet suspensif et l'assistance judiciaire.
La cour cantonale a déclaré n'avoir pas d'observations particulières à formuler et a conclu au rejet du recours. Le ministère public s'est déterminé et a conclu au rejet du recours.

Considérant en droit:
1.
En vertu de l'art. 105 de la loi fédérale sur l'entraide internationale en matière pénale (EIMP; RS 351.1), la décision d'exequatur incombe au juge compétent selon l'<ref-law>, qui statue sur l'exécution après avoir renseigné le condamné sur la procédure et l'avoir entendu en présence de son mandataire. L'<ref-law> définit une compétence à raison du lieu. L'autorité judiciaire qui doit statuer correspond à l'autorité de recours du canton compétent (cf. <ref-law>; HORST SCHMITT, in Basler Kommentar, Schweizerische Strafprozessordnung, 2011, n° 5 ad <ref-law>; MOREILLON/PAREIN-REYMOND, Petit commentaire, Code de procédure pénale, 2013, n° 5 ad <ref-law>; NIKLAUS SCHMID, Schweizerische Strafprozessordnung, Praxiskommentar, 2009, n° 7 ad <ref-law>). La décision rendue n'équivaut pas à une décision d'entraide au sens étroit qui ne pourrait être soumise que restrictivement au Tribunal fédéral (cf. <ref-law>). Il s'agit bien d'une décision d'exécution susceptible d'un recours en matière pénale en vertu de l'<ref-law> (cf. SCHMITT, op. cit., n° 6 ad <ref-law>; MOREILLON/PAREIN-REYMOND, ibidem; SCHMID, ibidem). Dès lors que l'exequatur implique d'examiner au regard des <ref-law> certaines conditions relevant du droit pénal interne, la compétence pour traiter le recours en matière pénale revient à la Cour de droit pénal du Tribunal fédéral (<ref-law>; cf. aussi arrêt 6B_300/2013 du 3 juin 2013 consid. 1).
En l'espèce, l'autorité de recours du canton n'a pas statué en instance unique comme spécifié ci-dessus mais le recourant a bénéficié d'une double instance cantonale. Il n'en subit aucun préjudice. Contre la décision rendue en dernière instance cantonale, un recours en matière pénale est ouvert.
2.
Invoquant en particulier une violation de l'art. 96 let. c EIMP, le recourant soutient que le jugement albanais ne peut être exécuté en Suisse.
2.1.
2.1.1. En vertu de l'art. 1 al. 1 let. d EIMP, la coopération internationale en matière pénale inclut l'exécution de décisions pénales étrangères, régie par les <ref-law>. L'<ref-law> énumère les situations où la coopération est irrecevable en introduisant notamment une clause générale qui permet à la Suisse de refuser la coopération lorsque la procédure à l'étranger présente d'autres défauts graves (let. d). Cela peut être le cas d'un jugement rendu par défaut dans l'Etat requérant si le condamné n'a en particulier pas bénéficié des garanties minimales de la défense. Il convient de procéder à une appréciation au regard des standards déduits des art. 29 al. 1 Cst. et 6 CEDH (cf. ROBERT ZIMMERMANN, La coopération judiciaire internationale en matière pénale, 3 e éd. 2009, n o 680 ss, spéc. 687). En matière d'exécution de jugement étranger, l'art. 96 let. c EIMP prévoit expressément que le juge refuse l'exequatur en totalité ou en partie s'il estime que le condamné a de bonnes raisons de s'opposer à l'exécution d'une décision ou d'une ordonnance pénale rendue par défaut qui n'est plus susceptible de recours ou d'opposition selon le droit de l'Etat requérant. L'art. 40 de l'ordonnance sur l'entraide internationale en matière pénale (OEIMP; RS 351.11) précise que les décisions pénales rendues dans l'Etat de condamnation sur opposition ou appel de la personne condamnée ne sont pas considérées comme des jugements par défaut.
2.1.2. Selon la jurisprudence de la Cour européenne des droits de l'homme, l'art. 6 CEDH garantit à l'accusé le droit d'être jugé en sa présence. Il s'ensuit qu'une procédure par défaut n'est compatible avec cette disposition que si le condamné a la possibilité de demander qu'une juridiction statue à nouveau, après l'avoir entendu, sur le bien-fondé de l'accusation, en fait comme en droit (arrêt de la CourEDH Sejdovic contre Italie du 1 er mars 2006, Recueil CourEDH 2006-II p. 201 § 81 s. et les arrêts cités).
Ce principe supporte cependant quelques atténuations. D'abord, la Cour européenne reconnaît que, devant les juridictions supérieures, la comparution de l'accusé ne revêt pas nécessairement la même importance qu'en première instance (cf. arrêt de la CourEDH Kamasinski contre Autriche du 19 décembre 1989, série A vol. 168 § 1060). Ensuite, elle admet que la CEDH n'empêche pas une personne de renoncer de son plein gré aux garanties d'un procès équitable de manière expresse ou tacite, en particulier à son droit d'être jugé en contradictoire. Elle exige seulement que la renonciation au droit de participer à l'audience se trouve établie de manière non équivoque et qu'elle ait été entourée du minimum de garanties correspondant à sa gravité (arrêt Sejdovic, § 86 et les arrêts cités). Enfin, sous réserve que les sanctions procédurales prévues ne soient pas disproportionnées et que l'accusé ne soit pas privé du droit d'être représenté par un avocat, la Cour européenne juge que le législateur national doit pouvoir décourager les absences injustifiées aux audiences (arrêt Sejdovic, § 92 et les arrêts cités, en particulier arrêt de la CourEDH Poitrimol contre France du 23 novembre 1993, série A vol. 277 A § 35). Dès lors, la Cour européenne des droits de l'homme admet qu'une personne condamnée par défaut se voie refuser la possibilité d'être jugée en contradictoire si les trois conditions cumulatives suivantes sont remplies: premièrement, il est établi que cette personne avait reçu sa citation à comparaître; deuxièmement, elle n'a pas été privée de son droit à l'assistance d'un avocat dans la procédure par défaut; et, troisièmement, il est démontré qu'elle avait renoncé de manière non équivoque à comparaître ou qu'elle avait cherché à se soustraire à la justice (cf. arrêts de la CourEDH Medenica contre Suisse du 14 juin 2001, Recueil CourEDH 2001-VI § 55 ss et Sejdovic, § 105 ss, a contrario). A propos de cette dernière condition, la Cour européenne a précisé qu'il ne devait pas incomber à l'accusé de prouver qu'il n'entendait pas se dérober à la justice ou que son absence s'expliquait par un cas de force majeure, mais qu'il était loisible aux autorités nationales d'évaluer si les excuses fournies par l'accusé pour justifier son absence étaient valables ou si les éléments versés au dossier permettaient de conclure que l'absence de l'accusé aux débats était indépendante de sa volonté (arrêt Sejdovic, § 88 et les arrêts cités; cf. aussi arrêts 6B_268/2011 du 19 juillet 2011 consid. 1.1; 6B_860/2008 du 10 juillet 2009 consid. 4.1).
2.2. Il ressort des constatations cantonales que la procédure étrangère dirigée contre le recourant a fait l'objet d'un premier jugement de condamnation le 14 septembre 2004, confirmé en appel le 17 octobre 2005, qui a été annulé le 4 avril 2007 par la Cour suprême d'Albanie qui a considéré que le recourant n'avait pas été cité régulièrement. Dans le cadre de la reprise, il est apparu, notamment sur la base d'une note de la police adressée au tribunal, que le recourant résidait en Suisse, son avocat ignorant cependant son adresse. Le tribunal a constaté le défaut du recourant et a poursuivi l'audience, la défense de celui-ci étant assurée par ledit avocat. Par jugement du 12 mai 2008, le tribunal a reconnu le recourant coupable non pas d'escroquerie mais de "non-dénonciation au crime" selon l'art. 300 du code pénal albanais et l'a condamné à une amende de 1'000'000 ALL. A la suite de l'appel du ministère public, la cour d'appel a constaté que le recourant faisait défaut mais qu'il était défendu par l'avocat précité qui était un avocat de choix, l'a reconnu coupable d'"escroquerie ayant entraîné de graves conséquences" selon l'art. 143 du code pénal albanais et l'a condamné à une peine de sept ans de prison (cf. arrêt attaqué, p. 3 et 4).
2.3. La cour cantonale a exposé que le recourant avait été défendu durant toute la procédure de 2004 à 2010 par le même avocat, qu'il n'avait jamais informé les autorités de poursuite pénale albanaise du fait qu'il habitait en Suisse, que ses déclarations selon lesquelles il ignorait l'existence de la procédure n'étaient pas crédibles, qu'il avait choisi de ne pas participer personnellement à cette procédure au vu du risque d'arrestation qui existait, mais de s'y faire représenter, qu'il devait en assumer les conséquences, d'autant que son avocat avait exercé de façon suffisante les droits de la défense (cf. arrêt attaqué p. 10).
2.4. Contrairement à ce que semble supposer la cour cantonale, la première phase de la procédure albanaise n'est pas déterminante dès lors que la Cour suprême de ce pays a retenu un vice dans la convocation et a renvoyé la cause en première instance pour une nouvelle procédure. Il convient donc uniquement de considérer la situation à partir de cette phase. Au moment de la reprise de la procédure, il ressort des constatations cantonales que la juridiction albanaise de première instance savait que le recourant se trouvait en Suisse et qu'il n'était pas atteignable à l'adresse de sa mère en Albanie. Son avocat ignorait son adresse en Suisse. Il n'apparaît pas que des démarches auraient été entreprises pour atteindre le recourant. Il n'apparaît pas plus que son avocat aurait eu un quelconque contact avec celui-ci. Dans ces conditions, il n'est pas établi de manière non équivoque que le recourant aurait renoncé au droit de participer à la procédure après avoir valablement reçu sa citation à comparaître. Rien n'atteste non plus que le recourant aurait entretenu un contact avec son avocat. Les éléments du dossier ne permettent pas de retenir que le recourant a bénéficié d'une procédure admissible au regard des exigences jurisprudentielles précitées (cf. supra consid. 2.1.2). Il s'ensuit que l'exequatur doit être refusée en vertu de l'art. 96 let. c EIMP. L'arrêt attaqué sera réformé en conséquence, la cause étant par ailleurs renvoyée à l'autorité précédente pour nouvelle décision sur les frais et indemnité de la procédure cantonale.
3.
Vu l'issue de la procédure, il n'est pas perçu de frais (<ref-law>) et le canton de Genève versera en mains du conseil du recourant une indemnité de dépens pour la procédure devant le Tribunal fédéral (art. 68 al. 1 et 2 LTF). La requête d'assistance judiciaire est ainsi sans objet.
La cause étant jugée, la requête d'effet suspensif est sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est admis et l'arrêt attaqué est réformé en ce sens que la requête d'exequatur est rejetée.
2.
La demande d'assistance judiciaire est sans objet.
3.
Il n'est pas perçu de frais judiciaires.
4.
Le canton de Genève versera à l'avocat du recourant une indemnité de 3'000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
5.
La cause est renvoyée à l'autorité précédente pour nouvelle décision sur les frais de procédure et dépens des instances cantonales.
6.
Le présent arrêt est communiqué aux parties et à la Cour de justice du canton de Genève, Chambre pénale d'appel et de révision.
Lausanne, le 5 septembre 2013
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Livet