Why does the speed of sound decrease at high altitudes although the air density decreases?

Wikipedia gives a pretty much straightforward answer. In an ideal gas, the speed of sound depends only on the temperature:

$$ v = \sqrt{\frac{\gamma \cdot k \cdot T}{m}} $$

So it neither decreases, nor increases with altitude, but just follows air temperature as can be seen in this graph:

The speed of sound in a gas is given by $\sqrt{ \dfrac {\gamma \,P}{\rho}}= \sqrt{\gamma \, R \, T}$ where the temperature, $T$, is in kelvin, $\gamma$ is the ratio of the specific heat capacities of a gas at constant pressure and constant volume and $R$ is the specific gas constant.

With increasing altitude there is a decrease in the density but also a decrease in the pressure, but not at the same rate because there is also a change in the temperature.

As the altitude increases, the temperature decreases and so does the speed of sound and then when the temperature increases so does the speed.

Source - Engineering Toolbox

Sound is simply a compression wave. The velocity of the wave is inversely related to the square root of fluid pressure, and directly proportional to the materiel’s Young modulus. A lower density means a lower pressure, which increases the wave velocity as you noticed.

Traveling through a compressible medium such as air, the simple equation for the velocity (v) of a compression wave is the square root of the Young’s modulus (B) divided by pressure (p)

$$v=\sqrt{\frac{B}{p}}.$$

Please see the following link for the derivation of this formula.

https://youtu.be/qVusackhzBs

But as the materiel becomes less dense, it reduces the surface area where the force is applied, the Young modulus decreases.

Increasing altitude thins the air out (reduces the surface area over which the force is applied) faster than it reduces pressure, resulting in a net decrease in the ratio, and therefore wave speed.