Based on this Quora answer, you may want to try something with a bit more complexity. $M \sim \alpha + \beta_1 z + \beta_2 z^2$ is a suggestion in this article, though I personally wouldn't go this route right away. You should check your residuals to see if you are missing some higher-order relationship. This could indicate "A missing higher-order term of a variable in the model to explain the curvature." Since you only have one predictor, finding which explanatory variable is missing a higher term would be pretty easy. Unfortunately, a pattern in your residuals could also indicate a missing explanatory variable. This is why I would not advise jumping to this method without some further checking.
Unfortunately, since you are only looking at two dimensions (magnitude, redshift), there is little you can do. This is pretty helpful for your specific case, I believe. A quote from the article:
In some cases, it’s possible that additional predictors can increase the true explanatory power of the model. However, in other cases, the data contain an inherently higher amount of unexplainable variability. For example, many psychology studies have R-squared values less that 50% because people are fairly unpredictable.
Without additional predictor variables to add dimensionality, it would be difficult to increase your $R^2$. Here is a link to an article discussing the significance of $R^2$. According to the author,
Just because effect size is small doesn’t mean it’s bad, unworthy of being interpreted, or useless. It’s just small. Even small effect sizes can have scientific or clinical significance. It depends on your field.
If the only point of the model was prediction, my client’s model would do a pretty bad job.
But it wasn’t. The point was to see if there was a small, but reliable relationship. And there was.
If you were looking to draw some sort of conclusion from the aggregate data, you could do this with a low $R^2$. Prediction could prove problematic, though. One last quote, this time from a different statistics blog, explaining that you may be able to draw meaningful conclusions from your model, just not predict very well:
A low R-squared is most problematic when you want to produce predictions that are reasonably precise (have a small enough prediction interval). How high should the R-squared be for prediction? Well, that depends on your requirements for the width of a prediction interval and how much variability is present in your data. While a high R-squared is required for precise predictions, it’s not sufficient by itself.