Объяснение для новичка с углублением с CLR.
Такой синтаксис придумали использовать в C# для вызова
конструктора.
Конструктор после компиляции - это метод с именем ".ctor" — из-за этого его нельзя просто-так руками объявить или вызвать.
Есть язык F#, в котором конструктор вызывается без new — на нём бы ваш пример выглядел так:
a[Random().Next(0, a.Length)]
Конструкторы нужны чтобы инициализировать экземпляры объектов.
Я бы посоветовал вам вынести Random в новую переменную, чтобы не пересоздавать его каждый раз, когда вы хотите вытащить случайный элемент массива.