Sachverhalt:
A.
X._ reiste im Jahr 2008 in die Schweiz ein und stellte ein Asylgesuch. Auf sein Gesuch wurde nicht eingetreten und er wurde aus der Schweiz weggewiesen. Der Wegweisung leistete X._ keine Folge. Am 13. Juli 2009 wurde er mit Strafbefehl der Staatsanwaltschaft Zürich-Sihl wegen rechtswidrigen Aufenthalts zu einer bedingten Geldstrafe von 60 Tagessätzen verurteilt. Vom 14. Juli 2009 bis zum 3. März 2010 befand er sich in Ausschaffungshaft. Am 21. Juni 2010 wurde er von der Staatsanwaltschaft See/Oberland erneut des rechtswidrigen Aufenthalts schuldig gesprochen. Unter Einbezug des Strafbefehls vom 13. Juli 2009 wurde ihm als Gesamtstrafe eine unbedingte Freiheitsstrafe von 90 Tagen auferlegt. Diese Strafe wurde im Jahr 2010 vollzogen. Mit Abwesenheitsurteil vom 21. Dezember 2012 sprach das Kriminalgericht Luzern X._ der versuchten räuberischen Erpressung, der Sachbeschädigung, der rechtswidrigen Einreise und des rechtswidrigen Aufenthalts schuldig und verurteilte ihn zu einer unbedingten Freiheitsstrafe von 18 Monaten. Am 24. März 2013 stellte X._ erneut ein Asylgesuch. Dieses wurde vom Bundesamt für Migration abgewiesen. Die dagegen erhobene Beschwerde ist zurzeit beim Bundesverwaltungsgericht hängig. X._ wurde am 28. September 2013 festgenommen. Gleichentags trat er den Vollzug der vom Kriminalgericht Luzern verhängten Freiheitsstrafe an.
B.
Das Kreisgericht St. Gallen sprach X._ am 19. Juni 2014 erneut des rechtswidrigen Aufenthalts schuldig und bestrafte ihn mit einer unbedingten Freiheitsstrafe von drei Monaten, teilweise als Zusatzstrafe zum Urteil des Luzerner Kriminalgerichts. Das Kantonsgericht St. Gallen bestätigte das erstinstanzliche Urteil.
C.
X._ führt Beschwerde in Strafsachen. Er beantragt, der Entscheid des Kantonsgerichts St. Gallen vom 13. November 2014 sei aufzuheben und er sei unter Gewährung des bedingten Strafvollzugs zu einer Geldstrafe von 90 Tagessätzen zu verurteilen. Eventualiter sei der vorinstanzliche Entscheid aufzuheben und es sei die Sache zur Festsetzung einer angemessenen Strafe unter Gewährung des bedingten Strafvollzugs an die Vorinstanz zurückzuweisen.

Erwägungen:
1.
Der Beschwerdeführer wendet sich gegen die Nichtgewährung des bedingten Strafvollzugs und die Strafart (Freiheitsstrafe). Er rügt eine Verletzung von Art. 40, 41 und 42 StGB.
2.
Gegenstand des Urteils des Kriminalgerichts Luzern vom 21. Dezember 2012 bildete der rechtswidrige Aufenthalt zwischen dem 22. Juni 2010 und dem 20. Oktober 2011. Im zu beurteilenden Fall erstreckt sich der Deliktszeitraum vom 21. Oktober 2011 bis zum 23. März 2013. Er liegt damit teils vor und teils nach der Verurteilung durch das Kriminalgericht Luzern, weshalb grundsätzlich eine teilweise Zusatzstrafe in Frage kommt. Die Vorinstanz spricht denn auch eine solche aus. Da die Bildung einer Zusatz- respektive einer neuen Gesamtstrafe nur möglich ist, wenn mehrere gleichartige Strafen ausgesprochen werden (vgl. <ref-ruling> E. 5.2 mit Hinweisen), begründet die Vorinstanz zunächst, weshalb auch für die neu zu beurteilenden Delikte einzig eine Strafe in der Form einer (kurzen unbedingten) Freiheitsstrafe (<ref-law>) in Betracht fällt. Erst danach erfolgt die eigentliche Strafzumessung, wobei die Vorinstanz eine teilweise Zusatzstrafe von drei Monaten Freiheitsstrafe ausspricht. Die Beanstandungen des Beschwerdeführers betreffen ausschliesslich den ersten Teil der Strafzumessung, d.h. die Erwägungen in Zusammenhang mit <ref-law>. Nicht beanstandet werden der Schuldspruch, das methodische Vorgehen bei der Strafzumessung sowie die Höhe der ausgefällten Strafe.
3.
Die Voraussetzungen für die Ausfällung einer kurzen unbedingten Freiheitsstrafe werden in <ref-law> umschrieben. Demnach kann das Gericht auf eine vollziehbare Freiheitsstrafe von weniger als sechs Monaten nur erkennen, wenn die Voraussetzungen für eine bedingte Strafe (<ref-law>) nicht gegeben sind und zu erwarten ist, dass eine Geldstrafe oder gemeinnützige Arbeit nicht vollzogen werden kann. Nach dem Prinzip der Verhältnismässigkeit soll bei alternativ zur Verfügung stehenden Sanktionen im Regelfall diejenige gewählt werden, die weniger stark in die persönliche Freiheit des Betroffenen eingreift bzw. die ihn am wenigsten hart trifft. Im Vordergrund steht daher auch bei Strafen von sechs Monaten bis zu einem Jahr die Geldstrafe als gegenüber der Freiheitsstrafe mildere Sanktion (<ref-ruling> E. 5.2; <ref-ruling> E. 4.1, 97 E. 4.2.2; je mit Hinweisen). Mit <ref-law> hat der Gesetzgeber für Strafen unter sechs Monaten eine gesetzliche Prioritätsordnung zugunsten nicht freiheitsentziehender Sanktionen eingeführt (BGE <ref-ruling> E. 4.1 mit Hinweis).
3.1. Gemäss <ref-law> schiebt das Gericht den Vollzug einer Geldstrafe, von gemeinnütziger Arbeit oder einer Freiheitsstrafe von mindestens sechs Monaten und höchstens zwei Jahren in der Regel auf, wenn eine unbedingte Strafe nicht notwendig erscheint, um den Täter von der Begehung weiterer Verbrechen oder Vergehen abzuhalten. Wurde der Täter innerhalb der letzten fünf Jahre vor der Tat zu einer Freiheitsstrafe von mindestens sechs Monaten oder zu einer Geldstrafe von mindestens 180 Tagessätzen verurteilt, so ist der Aufschub nur zulässig, wenn besonders günstige Umstände vorliegen (<ref-law>).
Die Prüfung der Bewährungsaussichten des Täters ist anhand einer Gesamtwürdigung aller wesentlichen Umstände vorzunehmen (vgl. dazu im Einzelnen <ref-ruling> E. 4.2.1). Dem Richter steht bei der Prüfung der Prognose des künftigen Legalverhaltens ein Ermessensspielraum zu. Das Bundesgericht greift nur ein, wenn das Ermessen über- bzw. unterschritten oder missbraucht und damit Bundesrecht verletzt wird (<ref-ruling>40 E. 4.2 mit Hinweis).
3.1.1. Die Vorinstanz erwägt, die unbedingt vollzogene Freiheitsstrafe sowie die rund siebenmonatige Ausschaffungshaft hätten keinen Eindruck auf den Beschwerdeführer gemacht. Zudem sei dieser während längerer Zeit untergetaucht. Zwar sei der Beschwerdeführer bedingt aus dem Strafvollzug entlassen worden. Der aktuelle Führungsbericht des Haft- und Untersuchungsgefängnisses Grosshof vom 27. Oktober 2014 falle jedoch überaus negativ aus. Der Beschwerdeführer habe sich weder an die Anordnungen des Personals noch an die Hausordnung gehalten. Sein Verhalten gegenüber dem Personal und den Mitgefangenen habe immer wieder zu Beanstandungen Anlass gegeben. Er habe nicht in die Gemeinschaft integriert werden können. Zeitweise habe sogar ein "Sondersetting" für ihn eingerichtet werden müssen. Schliesslich habe man die Integration in den Arbeitsprozess aufgrund mangelnder Arbeitsmotivation abgebrochen. Der Beschwerdeführer habe sich nie ernsthaft um eine Ausreise bemüht und die ihm obliegende Mitwirkung verweigert. Es sei davon auszugehen, dass er die Schweiz auch nicht verlassen würde, wenn ihm in den beiden laufenden Verwaltungsverfahren kein Aufenthaltstitel zuerkannt werden sollte. Dem Beschwerdeführer müsse insgesamt eine schlechte Legalprognose gestellt werden. Schon gar nicht könne von günstigen Umständen im Sinne von <ref-law> gesprochen werden.
3.1.2. Der Beschwerdeführer macht geltend, für die Prognosestellung dürfe nicht allein auf die bisherigen Verurteilungen abgestellt werden. Vielmehr müsse auch der Entwicklung in den vergangenen zwei Jahren Rechnung getragen werden. Er lebe seit über drei Jahren in einer gleichgeschlechtlichen Partnerschaft mit einem Schweizer. Die Partnerschaft sei am 23. Juli 2014 eingetragen worden. Im August 2014 habe er beim Migrationsamt St. Gallen ein Gesuch um Familiennachzug gestellt. Zudem habe er eine längere Haftstrafe absitzen müssen. Diese Erfahrung werde ihn von der Begehung weiterer Delikte abhalten. Die Trennung von seinem Lebenspartner während des Freiheitsentzugs sei hart gewesen und habe viel Kraft gekostet. Er sei sehr um Integration bemüht und werde dabei von seinem Partner unterstützt. Falls ihm eine Aufenthaltsbewilligung erteilt werde, könne er in dessen Firma arbeiten. Anschliessend wolle er versuchen, selbst eine Anstellung zu finden. Zum ersten Mal seit der Einreise in die Schweiz gebe es Stabilität und eine Zukunftsperspektive. Ihm sei eine äusserst günstige Prognose zu stellen und deshalb der bedingte Strafvollzug zu gewähren.
3.1.3. Die vorinstanzlichen Erwägungen in Zusammenhang mit der Gewährung respektive Nichtgewährung des bedingten Strafaufschubs sind nicht zu beanstanden. Der Beschwerdeführer wurde seit seiner Einreise im Jahr 2008 mehrfach des rechtswidrigen Aufenthalts schuldig gesprochen. Im Dezember 2012 wurde er zusätzlich wegen versuchter Erpressung und Sachbeschädigung zu insgesamt 18 Monaten Freiheitsstrafe verurteilt. Diese Verurteilung liegt innerhalb der letzten fünf Jahre (vgl. <ref-law>). Die persönliche Lage des Beschwerdeführers hat sich in den letzten Jahren verändert. Er lebt in einer gleichgeschlechtlichen Partnerschaft mit einem Schweizer. Die Partnerschaft ist seit 2014 im Zivilstandsregister eingetragen. Der Beschwerdeführer hat ein Gesuch um Familiennachzug (Art. 42 Abs. 1 i.V.m. Art. 52 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer [Ausländergesetz, AuG; SR 142.2]) gestellt. Zudem ist ein Asylverfahren hängig. Das Bundesamt für Migration hat dieses jedoch bereits abgewiesen. Ob das Gesuch um Familiennachzug bewilligt wird, ist wie von der Vorinstanz ausgeführt, ebenfalls ungewiss. Immerhin liegt aufgrund der Verurteilung zu einer längerfristigen Freiheitsstrafe ein Widerrufsgrund vor (vgl. Art. 51 Abs. 1 lit. b i.V.m. Art. 63 Abs. 1 lit. a und Art. 62 lit. b AuG; vgl. dazu <ref-ruling> E. 4.2). Da die Erteilung der Aufenthaltsbewilligung unter diesen Umständen, ohne damit der zuständigen Behörde vorgreifen zu wollen, keinesfalls sicher ist, kann der Beschwerdeführer daraus jedenfalls nichts zu seinen Gunsten ableiten. Ohnehin darf bei der Prognosebildung nicht auf ein einzelnes Kriterium abgestellt werden. Vielmehr ist eine Gesamtwürdigung sämtlicher Aspekte vorzunehmen, wobei die übrigen Umstände allesamt zu Ungunsten des Beschwerdeführers zu werten sind. Nebst der fortgesetzten Delinquenz fällt der Führungsbericht des Haft- und Untersuchungsgefängnisses Grosshof äusserst negativ ins Gewicht. Diesem kann entnommen werden, dass der Beschwerdeführer nicht in den Gefängnisalltag integriert werden konnte und es ihm an Arbeitsmotivation mangelte. Vor diesem Hintergrund ist höchst fraglich, ob der Beschwerdeführer nach einer allfälligen Erteilung einer Aufenthaltsbewilligung gewillt wäre, sich in den Arbeitsprozess sowie in die Gesellschaft zu integrieren und sich insgesamt wohl zu verhalten. Die Vorinstanz verletzt kein Bundesrecht, wenn sie von einer schlechten Legalprognose ausgeht und dem Beschwerdeführer den bedingten Strafvollzug nicht gewährt.
3.2.
3.2.1. Bezüglich der Strafart legt die Vorinstanz, teilweise unter Verweis auf das erstinstanzliche Urteil, ausführlich dar, weshalb sie auch für die neu zu beurteilenden Delikte einzig eine Freiheitsstrafe als zweckdienliche Sanktion erachtet. Konkret führt sie im Rahmen einer Vollstreckungsprognose aus, dass eine Geldstrafe nicht einbringlich wäre. Ausserdem habe der Beschwerdeführer trotz mehrerer Verurteilungen und Freiheitsentzüge wiederholt und hartnäckig delinquiert. Er sei unbelehrbar, weshalb weder eine Geldstrafe noch gemeinnützige Arbeit zweckmässige Sanktionen darstellen würden.
3.2.2. Der Beschwerdeführer wendet dagegen ein, da der bedingte Strafvollzug zu gewähren sei, sei die Strafe aufgrund des Strafmasses in Form einer Geldstrafe oder gemeinnütziger Arbeit auszufällen. Zudem sei ihm mit dem Vollzug der längeren Haftstrafe vor Augen geführt worden, welche Konsequenzen deliktisches Verhalten zeitige. Aus dieser Erfahrung werde er für die Zukunft seine Lehren ziehen.
3.2.3. Damit zeigt der Beschwerdeführer nicht auf, inwiefern das vorinstanzliche Urteil bundesrechtswidrig sein soll. Einerseits geht er von der falschen Prämisse der Gewährung des bedingten Strafvollzugs aus. Andererseits legt er nicht dar, inwiefern die vorinstanzliche Erwägung, wonach eine Geldstrafe oder gemeinnützige Arbeit nicht vollzogen werden könne, unrichtig sein soll. Die vorinstanzlichen Ausführungen hinsichtlich der Zweckmässigkeit der verhängten Sanktionsart sind überzeugend und nicht zu beanstanden. Darüber hinaus rügt der Beschwerdeführer weder das methodische Vorgehen der Vorinstanz bei der Strafzumessung noch das Aussprechen einer teilweisen Zusatzstrafe. Hätte die Vorinstanz, wie vom Beschwerdeführer gefordert, eine Geldstrafe aussprechen wollen, wäre die Bildung einer Gesamtstrafe aufgrund der ungleichartigen Strafen nicht zulässig gewesen und diese hätte kumulativ zur ersten Strafe verhängt werden müssen.
4.
Die Beschwerde ist abzuweisen. Die Gerichtskosten sind ausgangsgemäss dem Beschwerdeführer aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien und dem Kantonsgericht St. Gallen, Strafkammer, schriftlich mitgeteilt.
Lausanne, 4. Juni 2015
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Schär