Sachverhalt:
A.
Am 30. Juli 1975 wurde C.A._ der Neubau eines Wohnhauses mit Scheune auf dem Grundstück Nr. 575, Grundbuch Schüpfheim, bewilligt. Unter dem Titel besondere Bedingungen und Bemerkungen wurde dabei verfügt, dass das alte Wohnhaus auf dem genannten Grundstück abgerissen oder unbewohnbar gemacht werden müsse. Das alte Wohnhaus wurde jedoch weder abgerissen noch unbewohnbar gemacht, sondern wird seither als Ferienhaus vermietet (heute Grundstück Nr. 936, Grundbuch Schüpfheim).
B.
2016 reichte A.A._, Enkel des damaligen und Sohn des heutigen Eigentümers des betroffenen, ausserhalb der Bauzone liegenden Grundstücks, beim Gemeinderat Schüpfheim ein Gesuch um Feststellung der Verwirkung der Auflage aus der Baubewilligung vom 30. Juli 1975 zufolge Zeitablaufs sowie um Feststellung des Bestandesschutzes hinsichtlich des alten Wohnhauses ein. Das Regionale Bauamt Schüpfheim wies dieses Gesuch ab. Das Kantonsgericht Luzern stellte jedoch in einem Urteil von 2017 fest, dass die Anordnung, wonach das alte Wohnhaus abgerissen oder unbewohnbar gemacht werden müsse, aufgrund Zeitablaufs nicht mehr durchgesetzt werden könne. Dieses Urteil erwuchs unangefochten in Rechtskraft.
C.
Am 15. Mai 2018 reichten A.A._ und B.A._ ein Baugesuch betreffend Abbruch des bestehenden Wohnhauses mit Scheune und Neubau eines Einfamilienhauses mit Doppelgarage auf dem Grundstück Nr. 936, Grundbuch Schüpfheim, ein. Mit Entscheid vom 31. August 2018 verweigerte die Dienststelle Raum und Wirtschaft (rawi) des Bau-, Umwelt- und Wirtschaftsdepartements des Kantons Luzern die Ausnahmebewilligung für die Erstellung des Neubaus eines Einfamilienhauses ausserhalb der Bauzone. Eine dagegen erhobene Verwaltungsgerichtsbeschwerde wies das Kantonsgericht Luzern am 20. Dezember 2018 ab.
D.
Dagegen haben A.A._ und B.A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Sie beantragen, der Entscheid des Kantonsgerichts sei aufzuheben und es sei ihnen eine Ausnahmebewilligung nach Art. 24c RPG zu erteilen. Eventualiter sei die Sache zur Neubeurteilung im Sinne der Erwägungen des Bundesgerichts an die Vorinstanz zurückzuweisen.
Das Kantonsgericht und die Dienststelle rawi beantragen die Abweisung der Beschwerde. Das Bundesamt für Raumentwicklung (ARE) schliesst ebenfalls auf deren Abweisung.

Erwägungen:
1.
1.1. Gegen den kantonal letztinstanzlichen Endentscheid der Vorinstanz im Bereich des Baurechts steht die Beschwerde in öffentlichrechtlichen Angelegenheiten grundsätzlich offen (Art. 82 f. BGG). Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen und sind als Baugesuchsteller zur Beschwerdeführung legitimiert (<ref-law>). Auf die rechtzeitig erhobene Beschwerde ist daher grundsätzlich einzutreten.
1.2. Das Bundesgericht wendet das Bundesrecht (mit Ausnahme der Grundrechte) von Amtes wegen an (<ref-law>). Es ist daher nicht an die Begründung der Parteien gebunden, sondern kann die Beschwerde auch aus anderen als den geltend gemachten Gründen gutheissen oder den Entscheid mit einer Begründung bestätigen, die von jener der Vorinstanz abweicht (<ref-ruling> E. 1.4.1 S. 254 mit Hinweis).
1.3. Das Bundesgericht legt seinem Urteil den Sachverhalt zu Grunde, den die Vorinstanz festgestellt hat, sofern dieser nicht offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 105 und Art. 97 Abs. 1 BGG). Neue Tatsachen und Beweismittel können nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2.
Gemäss Art. 24c RPG (SR 700) werden bestimmungsgemäss nutzbare Bauten und Anlagen ausserhalb der Bauzonen, die nicht mehr zonenkonform sind, in ihrem Bestand grundsätzlich geschützt (Abs. 1). Solche Bauten und Anlagen können mit Bewilligung der zuständigen Behörde erneuert, teilweise geändert, massvoll erweitert oder wiederaufgebaut werden, sofern sie rechtmässig erstellt oder geändert worden sind (Abs. 2). Dies gilt auch für landwirtschaftliche Wohnbauten sowie angebaute Ökonomiebauten, die rechtmässig erstellt oder geändert worden sind, bevor das betreffende Grundstück Bestandteil des Nichtbaugebietes im Sinne des Bundesrechts wurde (Abs. 3). Veränderungen am äusseren Erscheinungsbild müssen für eine zeitgemässe Wohnnutzung oder eine energetische Sanierung nötig oder darauf ausgerichtet sein, die Einpassung in die Landschaft zu verbessern (Abs. 4). In jedem Fall bleibt die Vereinbarkeit mit den wichtigen Anliegen der Raumplanung vorbehalten (Abs. 5).
3.
Die Vorinstanz erwog, Art. 24c Abs. 2 RPG sei vorliegend nicht anwendbar. Das alte Wohnhaus sei mit dem Neubau im Jahr 1975 und der darauffolgenden Nutzung des alten Wohnhauses als Feriendomizil zonenwidrig geworden. Aufgrund des Eintritts der Zonenwidrigkeit durch eine Nutzungsänderung, und nicht durch eine Änderung der Nutzungsordnung, könne Art. 24c Abs. 2 RPG nicht angerufen werden.
Auch Art. 24c Abs. 3 RPG sei nicht anwendbar, da eine Kumulation der Möglichkeiten nach Art. 16a RPG und Art. 24c Abs. 3 RPG nicht möglich sei. Es sei auch nicht von Bedeutung, ob es sich bei der Anordnung, das alte Wohnhaus abzureissen, um eine Bedingung oder eine Auflage gehandelt habe, da es der Neubau gewesen sei, der die Nutzung des alten Hauses als Wohnhaus habe rechtswidrig werden lassen.
4.
Nach Ansicht der Beschwerdeführer hat die Vorinstanz Bundesrecht verletzt, indem sie verkannte, dass das alte Wohnhaus bereits mit dem Inkrafttreten des Gewässerschutzgesetzes per 1. Juli 1972 nicht mehr zonenkonform war, und den Beschwerdeführern mit dieser Begründung die Anwendung von Art. 24c Abs. 2 RPG verwehrte.
Auch die Ausführungen der Vorinstanz zu Art. 24c Abs. 3 RPG seien unzutreffend: Bei dessen Anwendung sei es gemäss Rechtsprechung des Bundesgerichts nicht von Belang, wie die Zonenwidrigkeit entstanden sei. Es spiele auch keine Rolle, ob die Verwendung des alten Wohnhauses als Feriendomizil der Auflage der Baubewilligung für das neue Wohnhaus widerspreche, da diese Auflage verwirkt sei. Einzig entscheidend sei vielmehr, dass das alte Wohnhaus rechtmässig erstellt und in der Folge nie geändert worden sei.
In diesem Zusammenhang rügen die Beschwerdeführer eine Verletzung der Begründungspflicht, weil das Kantonsgericht nicht geprüft habe, ob die Anordnung in der Baubewilligung von 1975 eine Auflage oder eine Bedingung sei. Eine Auflage als untergeordnete Nebenbestimmung vermöge nämlich die Rechtmässigkeit des alten Wohnhauses nicht zu beseitigen.
Indem die Vorinstanz festhielt, dass die Rechtswidrigkeit des alten Wohnhauses durch den Bau des neuen Wohnhauses entstanden sei, widerspreche sie sich selbst, da sie im Urteil von 2017 festgehalten habe, das alte Wohnhaus sei mit der Bewilligung des Ersatzbaus bzw. durch die Anordnung des Abrisses rechtswidrig geworden. Hierin liege eine Verletzung des Willkürverbots.
Schliesslich verletze die Vorinstanz ihre Begründungspflicht, wenn sie behaupte, es sei eine Kumulation der Möglichkeiten nach Art. 16a und Art. 24c Abs. 3 RPG vorgenommen worden, ohne dies weiter zu begründen. Die verbotene Kumulation betreffe einzig den Fall, wo jemand zuerst nach Art. 24c RPG eine Baubewilligung erhalte und zusätzlich noch um eine Baubewilligung nach Art. 16a RPG ersuche. Der umgekehrte Fall, wie er in casu vorliege, sei jedoch unproblematisch, womit Art. 24c Abs. 3 RPG anwendbar sei.
5.
Art. 24c Abs. 2 und 3 RPG enthalten eine erweiterte Besitzstandsgarantie, weil sie über die Wahrung des bisherigen Bestands hinaus auch die teilweise Änderung, massvolle Erweiterung und den Wiederaufbau von altrechtlichen Bauten erlauben (vgl. z.B. Urteil 1C_415/2014 vom 1. Oktober 2015 E. 3.7, in: ZBl 117/2016 S. 323; RDAF 2017 I S. 375 mit Hinweisen; <ref-ruling> E. 2.7 S. 517). Massgeblicher Vergleichszustand ist der Zustand, in dem sich die Baute oder Anlage im Zeitpunkt der Zuweisung zum Nichtbaugebiet befand (<ref-law> [SR 700.1]). Damit soll sichergestellt werden, dass die maximal zulässigen Änderungs- und Erweiterungsmöglichkeiten zwar möglicherweise in mehreren Etappen, insgesamt aber nur einmal ausgenutzt werden können. Wurden z.B. die nach <ref-law> höchstens zulässigen Erweiterungsmöglichkeiten durch eine frühere Baubewilligung ausgeschöpft, sind keine zusätzlichen Erweiterungen mehr möglich (ständige Rechtsprechung; vgl. z.B. Urteile 1A.186/2004 vom 12. Mai 2005 E. 6.2, in: ZBl 107/2006 S. 451 mit Hinweisen; 1C_347/2014 vom 16. Januar 2015 E. 3.5; Rudolf Muggli, in: Aemisegger/Moor/Ruch/Tschannen, Praxiskommentar RPG: Bauen ausserhalb der Bauzone, 2017, Art. 24c N. 34).
Gleiches gilt auch für den Wiederaufbau: Ein Eigentümer kann sich praxisgemäss nicht mehr auf die erweiterte Besitzstandsgarantie berufen für Bauten, für welche bereits die Errichtung einer Ersatzbaute bewilligt wurde. Mit dem Bau einer neuen zonenwidrigen Baute ist der Anspruch des Eigentümers auf Wahrung des Besitzstandes vollständig erschöpft (vgl. Urteil 1A.270/1992 vom 8. Juni 1993 E. 4a zur Vorgängerregelung in aArt. 24 Abs. 2 RPG). Die nochmalige Bewilligung einer Ersatzbaute würde nämlich - beim massgeblichen Vergleich mit dem Zustand im Zeitpunkt der Zuweisung zum Nichtbaugebiet - dazu führen, dass nicht eine, sondern zwei Ersatzbauten für dieselbe altrechtliche Baute bewilligt werden.
Diese Überlegungen treffen auch im vorliegenden Fall zu. Der damalige Eigentümer hat im Jahr 1975 eine Bewilligung erhalten, ein neues Wohnhaus zu errichten mit der Verpflichtung, das alte abzureissen. Mit dem Bau des neuen Wohnhauses wurde diese Bewilligung ausgenützt und der Anspruch auf Wahrung des Besitzstandes für das alte Wohnhaus vollständig erschöpft. Die Gesuchsteller können sich somit hinsichtlich des alten Wohnhauses nicht noch einmal auf die erweiterte Besitzstandsgarantie nach Art. 24c RPG berufen. Andernfalls würde ihnen ermöglicht, aus einem altrechtlichen Wohnhaus die Bewilligung für zwei oder sogar noch mehr zonenwidrige Neubauten zu erlangen. Dies ginge klar über die erweiterte Besitzstandsgarantie nach Art. 24c RPG hinaus.
Daran ändert auch die Feststellung des Kantonsgerichts von 2017 nichts, dass die Anordnung, wonach das alte Wohnhaus abgerissen werden oder unbewohnbar gemacht werde müsse, aufgrund Zeitablaufs nicht mehr durchgesetzt werden könne. Eine zu duldende Baute darf einzig mit bewilligungsfrei zulässigen Massnahmen unterhalten werden (Urteil 1C_558/2018 vom 9. Juli 2019 E. 4.3; 1C_486/2015 vom 24. Mai 2016 E. 3.3.3).
Vor diesem Hintergrund ist es auch nicht von Bedeutung, ob und wann das alte Wohnhaus rechtswidrig geworden ist und ob es sich bei der Anordnung in der Bewilligung von 1972 um eine Bedingung oder um eine Auflage gehandelt hat. Auf die weiteren Vorbringen der Beschwerdeführer muss somit nicht eingegangen werden.
6.
Nach dem Gesagten hat die Vorinstanz kein Bundesrecht verletzt, indem sie eine Ausnahmebewilligung gemäss Art. 24c RPG verweigert hat. Die Beschwerde ist abzuweisen.
Bei diesem Verfahrensausgang sind die Gerichtskosten den unterliegenden Beschwerdeführern aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 4'000.-- werden den Beschwerdeführern auferlegt.
3.
Dieses Urteil wird den Beschwerdeführern, dem Gemeinderat Schüpfheim, dem Bau-, Umwelt- und Wirtschaftsdepartement, Dienststelle Raum und Wirtschaft, dem Kantonsgericht Luzern, 4. Abteilung, und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 11. November 2019
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Die Gerichtsschreiberin: Hänni