X-ray diffraction, transmission electron microscopy, and magnetization measurements are employed to study the structural and magnetic properties of Mn-rich (Mn,Ga)As nanocrystals embedded in GaAs. These nanocomposites are obtained by moderate-temperature (400°C) and high-temperature (560°C and 630°C) annealing of (Ga,Mn)As layers with Mn concentrations between 0.1% and 2%, grown by molecular beam epitaxy at 270°C. Decomposition of (Ga,Mn)As is already observed at the lowest annealing temperature of 400°C for layers with initial Mn content of 1% and 2%. Both cubic and hexagonal (Mn,Ga)As nanocrystals, with similar diameters of 7-10 nm, are observed to coexist in layers with an initial Mn content of 0.5% and 2% after higher-temperature annealing. Measurements of magnetization relaxation in the time span 0.1-10 000 s provide evidence for superparamagnetic properties of the (Mn,Ga)As nanocrystals, as well as for the absence of spin-glass dynamics. These findings point to weak coupling between nanocrystals even in layers with the highest nanocrystal density.