Mosaic To New Raster makes an entirely new raster dataset, and projecting on the fly to create the output even if it worked would not give you enough control of the required resampling in my opinion. You are best off projecting all the inputs to the same coordinate system, using transformations if required (say, NAD83 to WGS84), and specifying an output cell size and registration point. Then Mosaic them together, or, perhaps better, creating a geodatabase mosaic dataset which doesn't require the time consuming mosaicking process.
However, the website you linked has very old DEMs (c. 2000). I highly recommend you instead obtain elevation data from the more current dataset published by the USGS at The National Map, which is available nationwide (excluding Alaska) seamlessly at 1/3 arc second (about 10m) resolution in geographic coordinates. These elevation datasets are much more current and higher quality (many based on lidar, not contours!) and are all in the same projection, so you can more easily combine them. The National Map elevation data are also in bigger tiles (1x1 degree) which will mean less work too!
For best results, I think you want to project the 1x1 degree tiles using the Project Raster tool to a common projection (specifying cell size and common registration point) and create a geodatabase mosaic dataset. It's usually very difficult to deal with a single raster file as large as you are planning.
Another thing to consider, you may be able to obtain this information from the Living Atlas without having to do any of this elevation data processing yourself. (Wow!)
Introducing Esri’s World Elevation Services
ArcGIS Pro even includes a ready to use tool that will calculate elevation slope and aspect from these services for you! (Wow, again!)
Summarize Elevation—Help | ArcGIS Desktop
Hope this helps.
