Sachverhalt: A. Die Swisscom (Schweiz) AG (nachfolgend: Swisscom) und die Sunrise Communications SA (nachfolgend: Sunrise) beabsichtigen, auf dem zur Autobahn A3 gehörenden und unter der Strassenhoheit und im Eigentum des Bundes stehenden Grundstück KTN 960 in Wollerau eine Mobilfunkanlage zu erstellen. Geplant sind fünf GSM 900/UMTS-Sendeantennen (zwei von Swisscom und drei von Sunrise) sowie Richtfunkantennen an einem 27 m hohen Mast und Technikschränke. Für die geplante Anlage ist am 7. Juni 2010 ein Baugesuch gestellt worden, gegen welches diverse Einsprachen eingingen. Am 8. Juli 2010 stimmte das Bundesamt für Strassen ASTRA dem Baugesuch unter Auflagen zu. Am 4. August 2010 reichten Swisscom und Sunrise eine Projektänderung ein. Das Amt für Raumentwicklung des Kantons Schwyz erteilte mit Gesamtentscheid vom 6. Oktober 2010 die kantonale Baubewilligung für das Bauvorhaben unter Auflagen und Nebenbestimmungen. Die Einsprachen wies es ab, soweit es darauf eintrat. Der Gemeinderat Wollerau hingegen verweigerte mit Beschluss vom 18. Oktober 2010 die Baubewilligung und hiess die Einsprachen teilweise gut. Zur Begründung erwog er insbesondere, der Antennenmast wirke aus Sicht des Orts- und Landschaftsbildschutzes störend. Gegen diesen Beschluss erhoben Swisscom und Sunrise am 11. November 2010 Beschwerde an den Regierungsrat des Kantons Schwyz. Dieser führte am 27. Oktober 2011 einen Augenschein vor Ort durch. Mit Beschluss vom 24. Januar 2012 hiess er die Beschwerde gut, hob den Beschluss des Gemeinderats Wollerau vom 18. Oktober 2010 auf und wies diesen an, die nachgesuchte Baubewilligung zu erteilen. Diesen Entscheid fochten diverse Personen beim Verwaltungsgericht des Kantons Schwyz an. Mit Entscheid vom 20. Juni 2012 wies dieses die Beschwerden ab. B. Mit Eingabe vom 14. September 2012 führen die im Rubrum aufgeführten, unterlegenen Personen Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Sie beantragen, es seien der Entscheid des Verwaltungsgerichts vom 20. Juni 2012 aufzuheben, die Baubewilligung zu verweigern und der abschlägige Baubescheid des Gemeinderats Wollerau vom 18. Oktober 2010 zu bestätigen. Mit Präsidialverfügung vom 22. Oktober 2012 hat das Bundesgericht der Beschwerde die aufschiebende Wirkung zuerkannt. Das kantonale Amt für Raumentwicklung und das Verwaltungsgericht verzichten auf Stellungnahmen zur Beschwerde. Der Regierungsrat beantragt die Beschwerdeabweisung. Swisscom und Sunrise beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Der Gemeinderat Wollerau stellt Antrag auf Gutheissung der Beschwerde. Das Bundesamt für Umwelt BAFU hat eine Vernehmlassung eingereicht, ohne ausdrücklich Anträge zu stellen. Das Bundesamt für Raumentwicklung ARE hat sich nicht vernehmen lassen. In ihrer Stellungnahme vom 24. Juni 2013 halten die Beschwerdeführer an ihrem Standpunkt und an ihren Anträgen fest.