Why do these parts being created move slower over time in a loop?

First off, I have to congratulate you: your code is honestly as good as it's possible to get as a beginner, and your question was informative and very well worded. That said, let's get into the problem.

Your issue here is that, basically, while loops suck, and are your issue. The correct way to handle repeated calls/loops in ROBLOX is with the game's "RunService". With it, you can essentially schedule functions to run at a constant-ish interval - usually 60 times per second. Using this service is almost ALWAYS better than using while - wait loops for game logic because it is more consistent and can provide MUCH better performance and clarity. Also, you can't have your game crash because of an infinite loop with no "wait()" :P.

First, some background on how it works. Essentially what you're doing when you use RunService is you're giving the game engine some code that you want it to run without your input over and over. It does this by "linking" the code you want to run in the form of a function to a so-called "event". That's what ":Connect" does in the code below. Every time the event is fired - 60 times per second in this case - your linked code is run! Easy! Events are SUPER powerful, and I highly suggest reading up on them.

So, let's replace your main while loop with RunService.

local debris = game:GetService("Debris")
local runService = game:GetService("RunService")

local cam = workspace.CurrentCamera
local rand = math.random
local num = 25

runService.Stepped:Connect(function() --This function/code will run at 60 times/second, instead of about 30 with "wait()"
	for i = 0, 5 do --Because of the better performance, create less parts per iteration
		local brick = Instance.new("Part")
		brick.Anchored = true
		brick.CanCollide = false
		brick.Size = Vector3.new(1, 1, 1)
		brick.CFrame = CFrame.new(cam.CFrame.Position + Vector3.new(rand(-num, num), rand(-num, num), rand(-num, num)))
		brick.Parent = workspace --Only set a part's parent to workspace AFTER all properties have been set for best performance.
		debris:AddItem(brick, 0.75)
	end
	--Notice we got rid of the wait(). It's not needed anymore!
end)

Notice that I omitted the code that animates the bricks above. Of course, we could just do a similar thing to the animation loop as we just did - replacing the while loop with an event connection - however, ROBLOX provides a much better way to do things like this - TweenService. (This is worth it, trust me!). TweenService basically handles animation in-game for you in an efficient and easy-to-understand way. Here's the code:

local tweenService = game:GetService("TweenService")
local cam = workspace.CurrentCamera
local rand = math.random
local num = 25
game:GetService("RunService").Stepped:Connect(function()
	for i = 0, 5 do
		local brick = Instance.new("Part")
		brick.Anchored = true
		brick.CanCollide = false
		brick.Size = Vector3.new(1, 1, 1)
		brick.CFrame = CFrame.new(cam.CFrame.Position + Vector3.new(rand(-num, num), rand(-num, num), rand(-num, num)))
		brick.Parent = workspace
		
		local tweenInfo = TweenInfo.new(.75,
			Enum.EasingStyle.Linear)
		local tween = tweenService:Create(brick, tweenInfo, {CFrame = brick.CFrame + Vector3.new(0,10,0)})
		tween.Completed:Connect(function() brick:Destroy() end)
		tween:Play()
	end
end)

Ok, let's go through what's going on here. The first new element is the call to TweenInfo.new(...), which gives us an object that can pass settings into the actual tween. In our case, we have set the duration of the tween to be .75 sec and the style of tween to be linear. Play around with these settings, you can find a full list on the wiki here. Next, we actually create the tween that will handle the animation for us with "tweenService:Create()". It takes the object to animate (The brick), the tweenInfo object we created earlier, and an object that describes a final property - In this case, we want our brick's final CFrame to be its current one offset vertically by 10 units. Then, we link a function that destroys the brick to the "Completed" event of the tween. This will, as you might expect, destroy the brick after the tween is finished animating. All that's left to do is start the animation, with "tween:Play()"! This, in the end, gets you buttery smooth animation with minimal (~5%) performance penalty!

Happy Coding!