Sachverhalt:
A.
Das Bezirksgericht Aarau verurteilte A._ am 12. Februar 2018 wegen Diebstahls, Sachbeschädigung und Hausfriedensbruchs zu 12 Monaten Freiheitsstrafe, als Gesamtstrafe mit einer im Umfang von 6 Monaten aufgeschobenen Freiheitsstrafe gemäss Urteil vom 14. Juni 2017, deren bedingten Vollzug das Bezirksgericht widerrief. Ausserdem ordnete es eine Landesverweisung von 6 Jahren an. Auf Berufung von A._ hin bestätigte das Obergericht des Kantons Aargau am 11. Februar 2019 das erstinstanzliche Urteil im Schuldpunkt, reduzierte aber die Gesamtfreiheitsstrafe auf 10 Monate und die Landesverweisung auf 5 Jahre.
B.
Mit Beschwerde in Strafsachen beim Bundesgericht beantragt A._, der angefochtene Entscheid sei hinsichtlich der Landesverweisung sowie der vorinstanzlichen Kostenregelung aufzuheben und zu neuer Entscheidung zurückzuweisen. Er ersucht um unentgeltliche Rechtspflege.
C.
Obergericht und Oberstaatsanwaltschaft des Kantons Aargau verzichten auf eine Stellungnahme.

Erwägungen:
1.
Der Beschwerde in Strafsachen gegen eine Landesverweisung im Sinne von Art. 66a StGB kommt in analoger Anwendung von Art. 103 Abs. 2 lit. b BGG von Gesetzes wegen aufschiebende Wirkung zu (Urteil 6B_235/2018 vom 1. November 2018, nicht publ. in: <ref-ruling>). Das entsprechende Gesuch des Beschwerdeführers ist damit gegenstandslos.
2.
Der Beschwerdeführer macht geltend, da er anerkannter Flüchtling sei, dürfe keine Landesverweisung angeordnet werden. Diese sei nicht erst beim Vollzug, sondern bereits bei der Härtefallprüfung zu berücksichtigen.
2.1.
2.1.1. Nach Art. 66a Abs. 1 lit. d StGB verweist das Gericht den Ausländer, der wegen Diebstahls in Verbindung mit Hausfriedensbruch verurteilt wird, unabhängig von der Höhe der Strafe für 5-15 Jahre des Landes. Es kann ausnahmsweise von einer Landesverweisung absehen, wenn diese für den Ausländer einen schweren persönlichen Härtefall bewirken würde und die öffentlichen Interessen an der Landesverweisung gegenüber den privaten Interessen des Ausländers am Verblieb in der Schweiz nicht überwiegen (Art. 66a Abs. 2 erster Satz StGB).
Gemäss Art. 66d Abs. 1 lit. a StGB kann der Vollzug der obligatorischen Landesverweisung nach Art. 66a StGB nur aufgeschoben werden, wenn der Betroffene ein von der Schweiz anerkannter Flüchtling ist und durch die Landesverweisung sein Leben oder seine Freiheit wegen seiner Rasse, Religion, Nationalität, Zugehörigkeit zu einer bestimmten sozialen Gruppe oder seiner politischen Anschauungen gefährdet wäre; davon ausgenommen ist der Flüchtling, der sich gemäss Artikel 5 Absatz 2 des Asylgesetzes vom 26. Juni 1998 (AsylG; SR 142.31) nicht auf das Rückschiebungsverbot berufen kann. Nach Art. 25 Abs. 3 BV dürfen Flüchtlinge nicht in einen Staat ausgeschafft werden, in dem sie verfolgt werden.
2.1.2. Nach bundesgerichtlicher Rechtsprechung hat das Gericht im Rahmen der Prüfung eines schweren persönlichen Härtefalls gemäss Art. 66a Abs. 2 StGB die öffentlichen und privaten Interessen gegeneinander abzuwägen. Die Beurteilung kann kriteriengeleitet nach der Bestimmung über den "schwerwiegenden persönlichen Härtefall" in Art. 31 Abs. 1 der Verordnung über Zulassung, Aufenthalt und Erwerbstätigkeit vom 24. Oktober 2007 (VZAE; SR 142.201) erfolgen. Zu berücksichtigen sind namentlich der Grad der (persönlichen und wirtschaftlichen) Integration, einschliesslich familiäre Bindungen des Ausländers in der Schweiz bzw. in der Heimat, Aufenthaltsdauer und Resozialisierungschancen. Ebenso ist der Rückfallgefahr und wiederholter Delinquenz Rechnung zu tragen. Das Gericht darf auch vor dem Inkrafttreten von Art. 66a StGB begangene Straftaten berücksichtigen. Die Härtefallklausel ist nach Intention und Gesetzeswortlaut restriktiv ("in modo restrittivo") anzuwenden (<ref-ruling> E. 3.3.1 ff.; Urteile 6B_841/2019 vom 15. Oktober 2019 E. 1.2; 6B_873/2018 vom 15. Februar 2019 E. 3.1; je mit Hinweisen).
Demgegenüber hat die Vollzugsbehörde - entgegen dem Wortlaut von Art. 66d StGB ("kann nur aufgeschoben werden") - kein Ermessen hinsichtlich der Frage, ob der Vollzug aufgeschoben wird. Sowohl aus dem zwingenden Charakter der völkerrechtlichen Verpflichtungen, die sich aus dem Rückschiebungsverbot ergeben, als auch aus der Diskussion im Vernehmlassungsverfahren muss vielmehr geschlossen werden, dass in diesen Fällen der Vollzug zwingend aufgeschoben werden muss (ZURBRÜGG/HRUSCHKA, Basler Kommentar, Strafrecht I, 4. Aufl. 2019, N. 5 f. zu Art. 66d StGB).
2.1.3. In der Lehre wird teilweise die Auffassung vertreten, dass die Auswirkungen eines Rückschiebungsverbots (sog. Non-Refoulement-Gebot) aufgrund völkerrechtlicher Normen, etwa von Art. 3 EMRK oder Art. 33 des Abkommens vom 28. Juli 1951 über die Rechtsstellung der Flüchtlinge (Flüchtlingskonvention [FK]; SR 0.142.30) bereits bei der Prüfung der Anordnung der Landesverweisung durch das Strafgericht erstmals berücksichtigt werden müssten (ZURBRÜGG/HRUSCHKA, a.a.O., N. 83 f. zu Vor Art. 66a-66d StGB; N. 42 ff. zu Art. 66a StGB und N. 5 f. zu Art. 66d StGB; Busslinger/Uebersax, Härtefallklausel und migrationsrechtliche Auswirkungen der Landesverweisung, in: Plädoyer 5/2016, S. 99; Münch/de Weck, Die neue Landesverweisung in Art. 66a ff. StGB, in: Anwaltsrevue 2016, S. 167). Die Landesverweisung komme demnach nur in Frage, wenn diese Prüfung ergebe, dass trotz Rückschiebungsverbot kein Aufenthaltsrecht bestehe, z.B. wegen der Schwere der Straftat, wobei sich eine Landesverweisung aber nur rechtfertige, wenn schwerwiegende Gründe den Ausschluss von der Flüchtlingseigenschaft nach Art. 1 Abschnitt F FK gebieten würden, oder sich die betroffene Person nicht auf das flüchtlingsrechtliche Rückschiebungsverbot gemäss Art. 33 Abs. 1 FK berufen könne. Ob eine Landesverweisung aufgrund völkerrechtlicher Normen ausscheide, sei demnach als Vorprüfung im Sinne eines sog. unechten Härtefalls vor dem echten Härtefall gemäss Art. 66a Abs. 2 StGB vorzunehmen. Bestehe hingegen ein Rückschiebungsverbot ohne (völkerrechtliches) Aufenthaltsrecht, sei nach Art. 66d StGB von den Migrationsbehörden der Vollzug aufzuschieben.
2.2.
2.2.1. Das Gesetz ist in erster Linie aus sich selbst heraus auszulegen, d.h., nach dem Wortlaut, Sinn und Zweck und den ihm zugrunde liegenden Wertungen auf der Basis einer teleologischen Verständnismethode. Die Gesetzesauslegung hat sich vom Gedanken leiten zu lassen, dass nicht schon der Wortlaut die Norm darstellt, sondern erst das an Sachverhalten verstandene und konkretisierte Gesetz. Gefordert ist die sachlich richtige Entscheidung im normativen Gefüge, ausgerichtet auf ein befriedigendes Ergebnis der ratio legis. Dabei befolgt das Bundesgericht einen pragmatischen Methodenpluralismus und lehnt es namentlich ab, die einzelnen Auslegungselemente einer hierarchischen Prioritätsordnung zu unterstellen. Die Gesetzesmaterialien sind zwar nicht unmittelbar entscheidend, dienen aber als Hilfsmittel, um den Sinn der Norm zu erkennen. Bei der Auslegung neuerer Bestimmungen kommt den Materialien eine besondere Stellung zu, weil veränderte Umstände oder ein gewandeltes Rechtsverständnis eine andere Lösung weniger nahelegen (<ref-ruling> E. 3.1.2; <ref-ruling> E. 3.3, 1 E. 2.4.1; <ref-ruling> E. 2.4; je mit Hinweisen).
2.2.2. Das Bundesgericht hat unter Verweis auf die in E. 2.1.3 zitierte Lehre erwogen, der mögliche Aufschub des Vollzugs der obligatorischen Landesverweisung durch die Vollzugsbehörden nach Art. 66d StGB schliesse nicht aus, dass Vollzugshindernisse bereits bei der Anordnung der Landesverweisung durch das Strafgericht zu berücksichtigen seien (Urteil 6B_651/2018 vom 17. Oktober 2018 E. 8.3.3). Im Urteil 6B_2/2019 vom 27. September 2019 E. 9.4 (zur Publ. vorgesehen) hat das Bundesgericht hierzu ausgeführt, das mit der Anordnung einer Landesverweisung befasste Gericht müsse - analog der Rechtsprechung im Ausländerrecht betreffend Wegweisung bzw. Entzug von Bewilligungen - prüfen, ob die Landesverweisung unter den konkreten Umständen verhältnismässig sei. Es dürfe die Frage nicht einfach der für den Vollzug zuständigen Behörde überlassen, wenn ein Rückweisungsverbot (das Non-refoulement-Gebot) oder andere zwingende völkerrechtliche Normen einer Landesverweisung entgegen stünden (vgl. auch Urteil 6B_1024/2019 vom 29. Januar 2020 E. 1.3.5). Bei der vom Strafgericht vorzunehmenden Prüfung sei namentlich dem Umstand Rechnung zu tragen, dass zufolge Art. 66c Abs. 2 StGB unbedingte Strafen oder Strafteile sowie freiheitsentziehende Massnahmen vor dem Vollzug der Landesverweisung zu vollziehen seien. Da aufgrund dessen zwischen der Anordnung und dem Vollzug der Landesverweisung eine relativ lange Zeit vergehen könne, müsse beachtet werden, dass sich die Umstände, welche einer Landesverweisung entgegen stünden - im vorliegenden Fall der Gesundheitszustand des Ausländers - ändern könnten. Wenn das Strafgericht aufgrund seiner Prüfung zum Schluss gelange, dass ein stabiler Zustand bestehe, welcher sich aller Vernunft nach nicht bessern werde, müsse es auf die Landesverweisung verzichten, falls sie sich als unverhältnismässig im Sinne von Art. 66a Abs. 2 StGB erweise. Umgekehrt könne die Landesverweisung verhältnismässig erscheinen, wenn der dieser entgegen stehende Zustand vorübergehender Natur oder - mit Blick auf die erörterten medizinischen Gründe - eine genügende Behandlung gewährleistet sei.
Aus dem vorstehend Gesagten folgt somit, dass das mit der Anordnung einer Landesverweisung befasste Strafgericht zwar die dieser möglicherweise entgegen stehenden Umstände beachten muss. Jedoch muss das Gericht - entgegen der Auffassung des Beschwerdeführers - bei Vorliegen eines solchen Umstands nicht zwingend auf die Anordnung einer Landesverweisung verzichten. Vielmehr ist konkret zu prüfen, ob sich eine Landesverweisung im Einzelfall als unverhältnismässig erweist, wobei der Verzicht nach ausdrücklichem Willen des Gesetzgebers grundsätzlich die Ausnahme bleiben soll (oben E. 2.1.2). Dies gilt, wie aus dem zitierten Urteil 6B_2/2019 vom 27. September 2019 (zur Publ. vorgesehen) erhellt, explizit auch für ein Rückschiebungsverbot resp. die vom Beschwerdeführer geltend gemachte Flüchtlingseigenschaft (vgl. dazu ausdrücklich auch das Urteil 6B_1024/2019 vom 29. Januar 2020 E. 1.3.5). Wie die Vorinstanz zutreffend ausführt, ist dabei zu beachten, dass sich die politische Situation im Zielland innerhalb des für die Landesverweisung relevanten Zeitraums von 5 - 15 Jahren massgeblich ändern kann, ebenso während der Dauer einer vorab zu vollziehenden Freiheitsstrafe oder freiheitsentziehenden Massnahme. Darauf hat auch das Bundesgericht im zur Publikation vorgesehenen Urteil 6B_2/2019 vom 27. September 2019 hingewiesen. Würde eine Landesverweisung bei anerkannten Flüchtlingen aufgrund der zum Entscheidzeitpunkt massgebenden Situation per se als unzulässig betrachtet, hätte dies ferner zur Konsequenz, dass ein Vollzug selbst bei nachträglichem Wegfall des Rückschiebungsverbots nicht mehr möglich wäre. Es erscheint indes stossend, dass ein Ausländer, der nach dem Willen des Gesetzgebers grundsätzlich zwingend des Landes hätte verwiesen werden müssen, bleiben dürfte, obwohl zum Zeitpunkt des möglichen Vollzugs kein Hinderungsgrund mehr besteht. Ferner wäre die Anordnung von Landesverweisungen bei anerkannten Flüchtlingen praktisch nicht mehr möglich. Der Vorinstanz ist zuzustimmen, dass auch dies augenscheinlich nicht im Sinne des Gesetzgebers gewesen sein kann. Aus den Materialien ergibt sich vielmehr, dass die Art. 66a ff. StGB zugrunde liegenden Verfassungsbestimmungen eine Verschärfung der bisherigen Rechtslage bezweckten (Botschaft vom 26. Juni 2013 zur Änderung des Strafgesetzbuchs und des Militärstrafgesetzes [Umsetzung von Art. 121 Abs. 3-6 BV über die Ausschaffung krimineller Ausländerinnen und Ausländer], BBL 2013 5975 S. 6008). Gleichfalls zutreffend ist schliesslich, dass primär die für den Vollzug der Landesverweisung zuständigen Behörden über das diesbezüglich notwendige Fachwissen und die nötige Erfahrung verfügen, um die entsprechenden Anordnungen zu treffen. Im Übrigen ist der völkerrechtlichen Verpflichtung des non-refoulement-Gebots sowie auch den Interessen des Betroffenen genüge getan, wenn diesen auf der Ebene des Vollzugs Rechnung getragen wird, solange dies notwendig ist. Für diese Sichtweise spricht nicht zuletzt die gesetzliche Systematik, die die Flüchtlingseigenschaft lediglich als Vollzugshindernis resp. als Aufschubsgrund nennt. Das vom Beschwerdeführer zitierte Urteil 6B_680/2018 vom 19. September 2018 E. 1.7 führt zu keinem anderen Ergebnis. Daraus kann nicht geschlossen werden, dass die Flüchtlingseigenschaft bereits der Anordnung der Landesverweisung entgegen stünde. Die Vorinstanz weist überdies zutreffend darauf hin, dass sich der Gesetzgeber der Problematik bewusst war, wonach des Landes verwiesene Ausländer über keinen aufenthaltsrechtlichen Status mehr verfügen, obwohl sie die Schweiz - aus den Vollzug hindernden Gründen - nicht verlassen (Botschaft, a.a.O.).
2.3. Die Vorinstanz hat es explizit abgelehnt, die Flüchtlingseigenschaft des Beschwerdeführers bei der Anordnung der Landesverweisung im Rahmen der Verhältnismässigkeitsprüfung zu berücksichtigen. Dies hätte sie aber nach dem Gesagten tun müssen und die Prüfung des Rückweisungsverbots nicht auf die Vollzugsbehörden abschieben dürfen. Nachdem die vorstehend zitierte, auch auf den vorliegenden Fall anzuwendende Rechtsprechung erst nach Erlass des angefochtenen Entscheids entwickelt wurde, ist der Vorinstanz insoweit kein Vorwurf zu machen. Mangels hinreichender Begründung des angefochtenen Urteils ist es dem Bundesgericht gleichwohl verwehrt, die Rechtmässigkeit resp. Verhältnismässigkeit der angeordneten Landesverweisung zu überprüfen. Diese Prüfung hat die Vorinstanz nachzuholen. Insbesondere ist darzulegen, ob und weshalb ihrer Auffassung nach die das Asyl des Beschwerdeführers begründenden Umstände einen stabilen Zustand darstellen, welcher sich aller Vernunft nach während des Strafvollzugs resp. der Dauer der Landesverweisung nicht bessern wird. Auf die Anordnung der Landesverweisung ist nur zu verzichten, wenn sie auch unter Berücksichtigung dieser Umstände, namentlich eines dauerhaften, unveränderlichen Rückweisungsverbots als unverhältnismässig erscheint. Dabei ist zu beachten, dass die Härtefallklausel gemäss Art. 66a Abs. 2 StGB nach dem Willen des Gesetzgebers restriktiv anzuwenden ist.
3.
Die Beschwerde ist gutzuheissen. Es sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Aargau hat Rechtsanwalt Franz Hollinger eine angemessene Entschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG). Das Gesuch um unentgeltliche Rechtspflege ist als gegenstandslos abzuschreiben.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Das angefochtene Urteil wird aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Aargau hat dem Rechtsvertreter des Beschwerdeführers, Rechtsanwalt Franz Hollinger, eine Parteientschädigung von Fr. 3'000.-- zu bezahlen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Aargau, Strafgericht, 1. Kammer, schriftlich mitgeteilt.
Lausanne, 17. März 2020
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Matt