Sachverhalt:
A.
A. und B. C._ erwarben 1995 ein Doppeleinfamilienhaus an der Oberlandstrasse 8 in Künten. Das Gebäude liegt auf der Parzelle Nr. 530 in der Wohnzone; die südöstliche Ecke des Hauses liegt auf der Grenze zur Landwirtschaftszone. Zugunsten der Parzelle Nr. 530 besteht eine Dienstbarkeit ("ausschliessliches und alleiniges Bepflanzungs- und Gestaltungsrecht" an 281 m2 der angrenzenden Parzelle Nr. 244, die der Landwirtschaftszone zugewiesen ist.
B.
Am 27. März 2014 reichten A. und B. C._ ein nachträgliches Baugesuch für ihre Gartenanlage (Sitzplätze, Pergola, Stützmauern, Gartenzaun etc.) ein, die sich im Wesentlichen auf Parzelle Nr. 244 in der Landwirtschaftszone befindet.
Das Aargauer Departement für Bau, Verkehr und Umwelt (BVU) wies das Gesuch am 10. September 2014 ab. Falls keine die Zonenwidrigkeit der Gartengestaltung beseitigende Umzonung des betroffenen Parzellenteils in der anstehenden Teilrevision der Nutzungsplanung zustandekomme, seien die erstellten Bauten und Anlagen der Gartengestaltung (Sitzplätze, Gartenplatten, Zaun, Mäuerchen, Pergola, Treppe, Stützbauten, Holzpodeste, Gerüst etc.) innert einer Frist von drei Monaten ab Rechtskraft der Nichtumzonung zu beseitigen und die betroffene Fläche zu rekultivieren.
Der Gemeinderat Künten forderte A. und B. C._ am 10. November 2014 auf, bis zum 20. Februar 2015 ein Umzonungsgesuch einzureichen; ohne ein solches Gesuch werde der Gemeinderat keine Teilrevision der Nutzungsplanung vornehmen und den Rückbau der Bauten verfügen.
C.
Mit Eingabe vom 12. Dezember 2014 erhoben A. und B. C._ Beschwerde beim Regierungsrat des Kantons Aargau gegen die Entscheide des BVU und des Gemeinderats Künten. Dieser überwies die Sache am 6. Januar 2015 antragsgemäss dem Verwaltungsgericht des Kantons Aargau (Sprungbeschwerde gemäss § 51 des Aargauer Verwaltungsrechtspflegegesetzes vom 4. Dezember 2007 [VRPG/AG; SAR 271.200]).
Das Verwaltungsgericht wies die Beschwerde am 25. August 2015 ab und setzte die Frist für die Einreichung eines Umzonungsgesuchs neu fest (drei Monate ab Rechtskraft des verwaltungsgerichtlichen Entscheids).
D.
Dagegen haben A. und B. C._ am 14. Oktober 2015 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, alle vorinstanzlichen Entscheide seien aufzuheben und die Wiederherstellung des ursprünglichen Zustands sei als verwirkt, evtl. als unverhältnismässig, zu erklären. Eventuell sei die Streitsache zur Durchführung eines Beweisverfahrens und zur Neuentscheidung an die Vorinstanz zurückzuweisen.
E.
Das Verwaltungsgericht und das BVU haben auf eine Vernehmlassung verzichtet. Der Gemeinderat Künten verweist auf seine Beschwerdeantwort vor Verwaltungsgericht.
Die Beschwerdeführer haben nicht repliziert.
F.
Mit Verfügung vom 10. November 2015 wurde der Beschwerde die aufschiebende Wirkung zuerkannt.

Erwägungen:
1.
Gegen den kantonal letztinstanzlichen Endentscheid des Verwaltungsgerichts steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht offen (Art. 82 lit. a, 86 Abs. 1 lit. d und 90 BGG). Die Beschwerdeführer sind als Baugesuchsteller zur Beschwerde legitimiert (<ref-law>). Auf die rechtzeitig erhobene Beschwerde (<ref-law>) ist daher grundsätzlich einzutreten (vorbehältlich nicht rechtsgenügend begründeter Rügen [vgl. <ref-law>]).
2.
Die Beschwerdeführer machen zunächst geltend, die Gartennutzung von 281 m2 der Parzelle Nr. 244 sei - zumindest dem Grundsatz nach - in der Baubewilligung vom 13. Februar 1995 mitbewilligt worden.
2.1. Das Verwaltungsgericht verneinte dies: In Ziff. II der Baubewilligung sei ausdrücklich festgehalten worden, dass ausserhalb des Baugebiets keine Bauten gestattet seien. Die Projektpläne hätten denn auch keinerlei Bauten und Anlagen ausserhalb der Zonengrenze vorgesehen, ebensowenig wie eine Gartengestaltung oder Bepflanzungen. Den Baugesuchsakten könne auch nicht entnommen werden, dass das Bauvorhaben nicht nur die Parzelle Nr. 430, sondern auch die Parzelle Nr. 244 beanspruchen würde. Insofern habe der Gemeinderat der Gartengestaltung bzw. -nutzung ausserhalb der Bauzone auch nicht zugestimmt oder diese bewilligt. Hinzu komme, dass der Gemeinderat für eine derartige Bewilligung zwingend die Zustimmung des zuständigen Departements hätte einholen müssen (§ 63 lit. e des Aargauer Baugesetzes vom 19. Januar 1993 [BauG/AG: SAR 713.100]; Art. 25 Abs. 2 RPG), was ebenfalls nicht geschehen sei.
2.2. Die dagegen vorgebrachten Einwände der Beschwerdeführer sind unbehelflich: Der Umstand, dass der Dienstbarkeitsteil der Parzelle Nr. 244 im Situationsplan 1:500 des Baugesuchs 1994 (zu Unrecht) als Teil der Bauparzelle Nr. 530 dargestellt und auch im Gelände markiert war, ändert nichts: Im Situationsplan war auch die Zonengrenze klar eingetragen; jenseits dieser Grenze sah das Baugesuch nichts vor, insbesondere war weder eine Gestaltung noch eine Nutzung als Garten eingezeichnet. Die Baubewilligung verlangte sogar ausdrücklich, dass infolge der etwas schwierig gestalteten Baugebietsabgrenzung die Absteckung des Schnürgerüsts bzw. deren Kontrolle durch den Kreisgeometer auszuführen sei (Ziff. III 2.8).
Soweit sich die Beschwerdeführer auf die fehlende Beanstandung des (in Rohplanie vorhandenen) Gartens bei der Bauabnahme 1995 berufen, kann dies keine formelle Baubewilligung ersetzen (zumal ohne Zustimmung des Kantons), sondern allenfalls für die Prüfung der Rechtmässigkeit von Wiederherstellungsmassnahmen eine Rolle spielen.
3.
Nach der bundesgerichtlichen Rechtsprechung verwirkt der Anspruch der Behörden auf Wiederherstellung des rechtmässigen Zustands im Interesse der Rechtssicherheit grundsätzlich nach 30 Jahren (<ref-ruling> E. 8 S. 367 mit Hinweisen). Den Kantonen steht es frei, kürzere Verwirkungsfristen vorzusehen (vgl. Urteil 1P.768/2000 vom 19. September 2001 E. 5b, in: ZBl 103/2002 S. 188; Pra 2002 Nr. 3 S. 9; RDAF 2003 I S. 395). Solche kürzeren Verwirkungsfristen können sich zudem aus Gründen des Vertrauensschutzes ergeben (<ref-ruling> E. 7 S. 365; <ref-ruling> E. 6.3 S. 39). Vorliegend sind weder 30 Jahre seit Bauabschluss verstrichen, noch sieht das Aargauer Recht eine kürzere (vertrauensschutzunabhängige) Verjährungs- oder Verwirkungsfrist vor.
Zu prüfen ist daher nur, ob Gründe des Vertrauensschutzes eine kürzere Verwirkungsfrist rechtfertigen. Dies kann namentlich der Fall sein, wenn die Behörden den baurechtswidrigen Zustand über Jahre hinaus duldeten, obwohl ihnen die Gesetzwidrigkeit bekannt war oder sie diese bei Anwendung der gebotenen Sorgfalt hätten kennen müssen (<ref-ruling> E. 7.1 mit Hinweisen).
3.1. Nach ständiger Rechtsprechung kann sich darauf aber nur berufen, wer selbst im guten Glauben gehandelt hat, d.h. angenommen hat und (unter Anwendung zumutbarer Sorgfalt) annehmen durfte, die von ihm ausgeübte Nutzung sei rechtmässig bzw. stehe mit der Baubewilligung in Einklang (<ref-ruling> E. 7.1 S. 365; <ref-ruling> E. 6.3 S. 35; je mit Hinweisen). Nichts anderes ergibt sich aus dem Urteil 1P.768/2000 vom 19. September 2001 (in: ZBl 103/2002 S. 188; Pra 2002 Nr. 3 S. 9; RDAF 2003 I S. 395), auf das sich die Beschwerdeführer berufen: In E. 5b ging es um eine kürzere kantonale Verwirkungsfrist kraft Zeitablaufs, die hier nicht zur Diskussion steht; für die kürzere Verwirkung kraft Vertrauensschutzes wurde (in E. 4c) am Erfordernis des guten Glaubens ausdrücklich festgehalten.
3.2. Das Verwaltungsgericht ging davon aus, dem Bauherrn als früherem Gemeinderat müsse aus der Baubewilligung vom 13. Februar 1995 klar gewesen sein, dass ausserhalb des Baugebiets nichts bewilligt worden war; ebenso habe er wissen müssen, dass dafür ausserhalb der Bauzonen zwingend eine kantonale Zustimmung erforderlich gewesen wäre. Die Beschwerdeführer müssten sich die Bösgläubigkeit des Bauherrn/Verkäufers anrechnen lassen. Zudem hätten sie auch bei den später von ihnen selbst erstellten Bauten nicht die zumutbare Sorgfalt angewendet: Nach der damals geltenden Allgemeinen Verordnung zum Baugesetz vom 23. Februar 1994 (ABauV) ergebe sich die Bewilligungspflicht einer Gartengestaltung ausserhalb der Bauzone klar. Es sei hinlänglich bekannt und hätte auch den Beschwerdeführern klar sein müssen, dass an Bauten und Anlagen in der Landwirtschaftszone rechtlich strengere Anforderungen gestellt würden als innerhalb der Bauzone. Dennoch hätten sich die Beschwerdeführer nie bei der zuständigen Behörde über die Zulässigkeit erkundigt.
3.3. Die Beschwerdeführer machen dagegen zunächst geltend, das Verwaltungsgericht hätte diese Feststellung nicht treffen dürfen, ohne zuvor den Bauherrn und den damaligen Bauamtschef der Gemeinde zu befragen. Es ist aber nicht ersichtlich, inwiefern deren Aussage zu einer anderen Beurteilung hätte führen können.
Selbst wenn es damals Praxis zahlreicher aargauischer Gemeinden gewesen wäre, bis an den Zonenrand bauen zu lassen und das anschliessende Land der Gartennutzung zuzugestehen, wie die Beschwerdeführer geltend machen, könnte dies (wenn überhaupt) allenfalls das Vertrauen begründet haben, das Land ohne bauliche Massnahmen zu privaten Zwecken nutzen zu dürfen (z.B. als Spielwiese, Obstgarten oder ähnliches), nicht aber, darauf Bauten und Anlagen ohne Bewilligung erstellen zu dürfen. Dem Bauherrn, als ehemaligem Gemeinderat, war die Notwendigkeit einer kantonalen Zustimmung für Bauten ausserhalb der Bauzone mit Sicherheit bekannt. Zudem hatte die Gemeinde Künten in der Baubewilligung vom 13. Febraur 1995 ausdrücklich festgehalten, dass keine Bauten ausserhalb der Bauzone zulässig seien. Es gibt keinerlei Anhaltspunkte dafür, dass sich dieser Satz - wie die Beschwerdeführer behaupten - nur auf Hochbauten bezog, nicht aber auf befestigte Sitzplätze, Mäuerchen, Treppen etc. Bei allfälligen Zweifeln über die Bedeutung der Bewilligung wäre der Baugesuchsteller verpflichtet gewesen, Rückfrage bei der zuständigen Behörde zu nehmen. Sofern er dies unterliess, kann er sich nicht mehr auf den Vertrauensschutz berufen (Urteil A.198/1978 vom 14. Februar 1979 E. 4b, in: ZBl 80/1979 312).
3.4. Nicht zu beanstanden ist die Auffassung des Verwaltungsgerichts, dass sich die Beschwerdeführer den bösen Glauben des Bauherrn anrechnen lassen müssen. Dies gilt jedenfalls, sofern sie sich auf die Baubewilligung 1995 berufen bzw. geltend machen, das Bauamt habe den bereits in Rohplanie erstellten Gartenraum bei der Rohbau- und Bezugskontrolle im August/September 1995 nicht beanstandet (zu den von ihnen selbst erstellten Bauten vgl. unten E. 3.5). Dies entspricht der bundesgerichtlichen Rechtsprechung und der bereits vom Verwaltungsgericht zitierten Literatur (vgl. zuletzt Urteil 1C_59/2011 vom 10. Mai 2011 E. 3.3 mit Hinweis auf Magdalena Ruoss Fierz, Massnahmen gegen illegales Bauen, Diss. Zürich 1999, S. 60 und S. 79 ff.; so schon <ref-ruling> E. 2b S. 316).
Dies gilt - entgegen der Auffassung der Beschwerdeführer - nicht nur für Fälle, in denen dem Verkäufer gegenüber bereits eine Beseitigungsverfügung erlassen worden ist: Grundsätzlich erhält der Rechtsnachfolger die Rechtsschutzmöglichkeiten seines Vorgängers nach dem jeweiligen Verfahrensstand, und kann sich (vorbehältlich nachträglicher Änderungen der Rechts- und Sachlage) gegen die Pflicht, eine widerrechtliche Baute abzubrechen, nur noch in dem Umfang wehren, als dies sein Rechtsvorgänger noch konnte (ALDO ZAUGG/ PETER LUDWIG, Baugesetz des Kantons Bern, Band I, 4. Aufl., Art. 46 Rz. 9b S. 548; RUOSS FIERZ, a.a.O. S. 84 f.). Der Rechtsnachfolger kann sich somit auf Zusicherungen der Behörde oder andere Vertrauenstatbestände berufen, die seinem Vorgänger gegenüber erteilt bzw. geschaffen wurden, muss sich aber dessen bösen Glauben anrechnen lassen (BEATRICE WEBER-DÜRLER, Vertrauensschutz im öffentlichen Recht, Basel/Frankfurt a.M. 1983, § 18 III S. 210).
3.5. Die meisten Bauten und Anlagen, die beseitigt werden müssen, wurden allerdings im Zeitraum 1996 bis 2004 von den Beschwerdeführern selbst errichtet. Hinsichtlich dieser Arbeiten hätten die Beschwerdeführer - auch und gerade als juristische Laien - bei der Baubehörde nachfragen müssen, bevor sie auf eigene Faust bauliche Veränderungen vornahmen. Soweit sie auf Aussagen anderer (Privat-) Personen vertrauten, kann dies von vornherein keinen Vertrauensschutz im Sinne von <ref-law> begründen, da dieser an das Vertrauen des Bürgers in ein staatliches Verhalten anknüpft (WEBER-DÜRLER, a.a.O., S. 79).
3.6. Unter diesen Umständen durfte das Verwaltungsgericht die Berufung auf den Vertrauensschutz schon aufgrund der fehlenden Gutgläubigkeit der Beschwerdeführer ausschliessen. Es konnte daher offenlassen, wann die kommunalen und/oder kantonalen Behörden Kenntnis von den illegalen Bauten und Anlagen erhielten und dagegen hätten einschreiten können bzw. müssen.
4.
Schliesslich halten die Beschwerdeführer den Rückbau aus verschiedenen Gründen für unverhältnismässig.
4.1. Zunächst machen sie geltend, die Wiederherstellung des ursprünglichen Geländeverlaufs sei nicht mehr möglich, weil sonst der Böschungsfuss ins Innere des Wohngebäudes zu liegen käme.
Tatsächlich gingen die Vorinstanzen davon aus, dass der ursprüngliche Geländeverlauf wiederherzustellen sei. Da sich die Verfügung aber nur auf die Gartenanlage und nicht auf das bestehende, formell bewilligte Wohngebäude bezieht, ist klar, dass der Rückbau nur soweit erfolgen kann und muss, als er Bestand und Nutzung des Wohnhauses nicht beeinträchtigt. Es wird Sache der Beschwerdeführer sein, den Behörden vor dem Rückbau Vorschläge zur möglichen Terraingestaltung einzureichen.
4.2. Die Beschwerdeführer schätzen die Wiederherstellungskosten auf 50 bis 100 Tausend Franken und den Wertverlust ihres Grundstücks auf 100 bis 200 Tausend Franken. Dies würde sie an den Rand des Ruins bringen.
Das Verwaltungsgericht räumte ein, dass die Wiederherstellung zu einer erheblichen Vermögensminderung der Beschwerdeführer führen würde (ohne diese zu beziffern). Diese hätten aber nicht in guten Treuen von der Zulässigkeit ihrer baulichen Investitionen ausgehen dürfen und daher auf eigenes Risiko gehandelt. Die Beschwerdeführer hätten seit rund 20 Jahren von der rechtswidrigen Situation profitiert, hätten aber keinen Anspruch darauf, diese auch in Zukunft fortzusetzen.
Diese Erwägungen sind keineswegs zynisch, wie die Beschwerdeführer geltend machen, sondern treffen zu: Die geltend gemachte Wertminderung des Grundstücks beseitigt lediglich eine Wertschöpfung, die durch die unzulässige bauliche Inanspruchnahme der Landwirtschaftszone entstanden ist und - bei korrektem Vorgehen - gar nicht eingetreten wäre. Hinzu kommt, dass die Wertminderung nur realisiert wird, wenn die Beschwerdeführer ihr Haus verkaufen wollten. Bleiben sie dort wohnen, so treffen sie nur (aber immerhin) die eigentlichen Rückbaukosten.
4.3. Die Beschwerdeführer halten das öffentliche Interesse an der Wiederherstellung des rechtmässigen Zustands für gering; dieses könne den massiven Eingriff in ihre Eigentumsfreiheit nicht rechtfertigen. Die Interessenabwägung des Verwaltungsgerichts sei einseitig, weil es nichts zu den Versäumnissen der Baubehörden der Gemeinde Künten sage. Die Einräumung der Möglichkeit, durch ein nachträgliches Einzonungsbegehren noch zur Rechtmässigkeit der Gartennutzung zu gelangen, sei rein theoretischer Natur und könne die Wiederherstellung höchstens hinauszögern.
Zunächst ist festzuhalten, dass es nicht Aufgabe des Verwaltungsgerichts war, wie eine Aufsichtsbehörde sämtliche Handlungen und Unterlassungen der Gemeindebehörden in dieser Angelegenheit zu überprüfen; deren Verhalten war nur insoweit zu berücksichtigen, als es für den Entscheid relevant war (vgl. oben E. 3.6). Es ist nicht ersichtlich, inwiefern allfällige Fehler des kommunalen Bauamts das öffentliche Interesse an der Beseitigung illegaler Bauten und Anlagen in der Landwirtschaftszone mindern, deren Nutzung bundesrechtlich geregelt ist (Art. 16 f. und 24 ff. RPG) und in erster Linie in der Zuständigkeit des Kantons liegt (§ 63 lit. e BauG/AG; Art. 25 Abs. 2 RPG).
Das Verwaltungsgericht hat zutreffend ausgeführt, dass die fragliche Gartengestaltung und -nutzung eine nicht unerhebliche Fläche von 281 m2 betrifft und ein gewichtiges öffentliches Interesse daran bestehe, eine schleichende Ausdehnung der Bauzonen ins Kulturland zu verhindern. Es mass dabei der präjudiziellen Bedeutung des Falls besondere Bedeutung bei. Zu Recht: Gerade wenn in der Vergangenheit in verschiedenen Aargauer Gemeinden die (unzulässige) Praxis bestand, den zu Wohnbauten gehörigen Umschwung und Erholungsraum im kostengünstigen Landwirtschaftsland zu schaffen, wie die Beschwerdeführer selbst vorbringen, ist es umso wichtiger, konsequent dagegen vorzugehen, d.h. systematisch den Rückbau und die Rekultivierung solcher Flächen zu verlangen. Dieses Interesse überwiegt die privaten Interessen der Beschwerdeführer.
Im Übrigen sind die Behörden den Beschwerdeführern bereits entgegengekommen, indem der Rückbau nur bedingt ausgesprochen wurde, für den Fall, dass die Zonenwidrigkeit der Gartengestaltung nicht durch die Umzonung des betroffenen Teils der Parzelle Nr. 244 in der anstehenden Teilrevision der Nutzungsplanung beseitigt werden kann. Selbst wenn diese Umzonung nicht zustande kommen sollte, stellt bereits der damit verbundene Aufschub des Rückbaus ein Zugeständnis zugunsten der Beschwerdeführer dar.
5.
Schliesslich rügen die Beschwerdeführer eine Verletzung des rechtlichen Gehörs (<ref-law>; § 22 Abs. 1 KV/AG), weil das Verwaltungsgericht ihre Beweisanträge abgelehnt habe.
Dieses ging davon aus, dass sich im Wesentlichen Rechtsfragen stellten und der Sachverhalt aufgrund der vorhandenen Akten genügend klar sei, um den Fall beurteilen zu können. Auf die Abnahme weiterer Beweismittel könne in antizipierter Beweiswürdigung verzichtet werden.
Nach ständiger Rechtsprechung liegt keine Verletzung des rechtlichen Gehörs vor, wenn ein Gericht auf die Abnahme beantragter Beweismittel verzichtet, weil es auf Grund der bereits abgenommenen Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 5.3 S. 236 mit Hinweisen).
Die Beschwerdeführer legen nicht dar, inwiefern ein Augenschein des Gerichts geboten gewesen wäre; dies ist auch nicht ersichtlich. Für die beantragten Einvernahmen des Verkäufers und des ehemaligen Bauverwalters der Gemeinde, aber auch der Beschwerdeführer selbst, kann auf das oben (E. 3.3) Gesagte verwiesen werden. Auch die beantragten Amtsberichte hätten nicht zu einer anderen Beurteilung der Verhältnismässigkeitsbeurteilung geführt (vgl. oben E. 4.3).
6.
Damit ist die Beschwerde abzuweisen. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kostenpflichtig und haben keinen Anspruch auf eine Parteientschädigung (Art. 66 und 68 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3.
Es werden keine Parteientschädigungen zugesprochen.
4.
Dieses Urteil wird den Beschwerdeführern, dem Gemeinderat Künten, dem Departement Bau, Verkehr und Umwelt des Kantons Aargau, Abteilung für Baubewilligungen, und dem Verwaltungsgericht des Kantons Aargau, 3. Kammer, schriftlich mitgeteilt.
Lausanne, 6. Januar 2016
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Gerber