Faits :
A.
A._, ressortissant algérien né 22 avril 1984, est arrivé illégalement en Suisse en 2008. Il a eu trois enfants, à savoir B._, C._ et D._, nés respectivement en 2011, 2013 et 2020, avec E._, née à Genève, enfants qu'il a reconnus. Celle-ci, également ressortissante algérienne, ainsi que ses enfants ont obtenu la nationalité suisse en 2016. En 2012, l'état civil compétent a déclaré irrecevable une demande formée en vue de mariage par les intéressés, faute de preuve de la légalité du séjour de A._ dans notre pays. Celui-ci a, en juillet 2012, déposé une demande d'autorisation de séjour sans activité lucrative.
Le 18 janvier 2013, A._ a été placé en détention préventive. Par arrêt du 26 septembre 2016, la Chambre pénale d'appel et de révision de la Cour de justice de la République et canton de Genève (ci-après: la Chambre pénale d'appel) l'a condamné à une peine privative de liberté de cinq ans et cinq mois pour tentative d'assassinat commise le 7 août 2011, ainsi que pour entrée et séjour illégaux du 1er janvier 2008 au 16 janvier 2013; elle a réduit la peine de six ans prononcée initialement en raison des conditions de détention de l'intéressé jugées illicites par le Tribunal fédéral (cause 6B_688/2015). A._ s'est vu octroyé la liberté conditionnelle, en date du 7 février 2017.
Le 27 juin 2017, l'état civil compétent a déclaré irrecevable une nouvelle requête d'ouverture de procédure en vue de mariage.
Le Ministère public de la République et canton de Genève a condamné A._ par ordonnance pénale du 29 septembre 2017 à une amende de 400 fr. pour conduite d'un véhicule en étant titulaire d'un permis de conduire étranger et consommation de stupéfiants. Puis, par jugement du 22 décembre 2017, la Chambre pénale d'appel a prononcé une peine de 120 jours-amende à 30 fr. pour dénonciation calomnieuse à l'égard d'un gardien de prison.
L'Office cantonal de la population et des migrations de la République et canton de Genève (ci-après: l'Office cantonal de la population) a délivré deux autorisations temporaires en vue de travailler à A._ en 2018 et 2019.
Après que E._ et A._ eurent relancé à plusieurs reprises l'Office cantonal de la population, cette autorité, en date du 10 mai 2019, a refusé d'octroyer une autorisation de séjour à celui-ci et lui a imparti un délai au 8 août 2019 pour quitter la Suisse.
B.
Par jugement du 1er décembre 2020, la Chambre administrative de la Cour de justice de la République et canton de Genève (ci-après: la Cour de justice) a rejeté le recours de A._ à l'encontre de la décision du 10 mai 2019 de l'Office cantonal de la population. Elle a en substance considéré que la condamnation du recourant à une peine privative de liberté de cinq ans et cinq mois pour tentative d'assassinat, ainsi que les deux autres condamnations pénales subséquentes prévalaient sur le lien étroit que celui-ci entretenait avec ses enfants; de plus, la majeure partie de son séjour en Suisse avait été illégale et il ne pouvait se prévaloir d'une intégration particulièrement réussie.
C.
Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du 1er décembre 2020 de la Cour de justice, de le mettre au bénéfice d'une autorisation de séjour, subsidiairement, de renvoyer la cause à l'Office cantonal de la population pour une nouvelle décision.
Ledit office a déclaré ne pas avoir d'observations à formuler. La Cour de justice persiste dans les considérants et le dispositif de son arrêt. Le Secrétariat d'Etat aux migrations n'a pas déposé d'écriture.
Par ordonnance du 21 janvier 2021, le Président de la IIe Cour de droit public a admis la demande d'effet suspensif.

Considérant en droit :
1.
Le recourant invoque l'art. 8 CEDH en se prévalant de sa relation étroite avec ses enfants qui ont la nationalité suisse et auprès desquels il vit. Dès lors que cette disposition est susceptible de fonder un droit à demeurer en Suisse, le recours en matière de droit public échappe au motif d'irrecevabilité de l'art. 83 let. c ch. 2 LTF.
Au surplus, le recours remplit les conditions des art. 42 et 82 ss LTF, de sorte qu'il convient d'entrer en matière.
Toutefois, l'attestation d'une psychologue datée du 1er février 2021 est irrecevable. Le Tribunal fédéral ne peut en effet pas tenir compte de faits ou de moyens de preuve survenus postérieurement au prononcé de la décision entreprise, c'est-à-dire de véritables nova (art. 99 al. 1 LTF; <ref-ruling> consid. 5.2.4).
2.
Le litige concerne l'octroi d'une autorisation de séjour.
2.1. Le recourant ne se prévaut, à bon droit, que de l'art. 8 CEDH et se plaint en particulier de le pesée des intérêts effectuée par l'autorité précédente (art. 8 par. 2 CEDH).
2.2. La Cour de justice a correctement exposé le droit applicable (art. 8 CEDH; art. 3 cum art. 9 de la Convention du 20 novembre 1989 relative aux droits de l'enfant [CDE; RS 0.107]) protégeant la vie familiale et les exigences relatives à l'ingérence dans le droit au respect de cette vie, ainsi que la jurisprudence y relative (<ref-ruling> consid. 2.3.3; <ref-ruling> consid. 2.2.2; <ref-ruling> consid. 4.3 ss); il y est, ainsi, renvoyé. On précisera, à cet égard, que le recourant vit en couple avec sa compagne depuis 2010, que les intéressés ont trois enfants et qu'ils ont déposé à deux reprises des demandes à l'état civil en vue de leur mariage. Ainsi, le recourant peut tirer un droit de l'art. 8 par. 1 CEDH non seulement en lien avec ses enfants mais également avec sa concubine (cf. arrêts 6B_124/2020 du 1er mai 2020 consid. 3.2.2; 2C_72/2019 du 7 juin 2019 consid. 6.1).
2.3. Par jugement du 27 décembre 2017, la Chambre pénale d'appel a condamné le recourant à une peine privative de liberté de cinq ans et cinq mois pour tentative d'assassinat et pour entrée et séjour illégaux, réduisant la peine initialement prononcée de six ans de quelques mois en raison des conditions de détention de l'intéressé jugées illicites. Selon les faits de l'arrêt entrepris, le recourant s'était rendu coupable, en qualité de coauteur, de tentative d'assassinat; sa faute était très grave, car il s'en était pris à l'intégrité physique d'autrui avec la plus grande lâcheté, sans aucune raison; le caractère odieux de son comportement et de celui de ses comparses avait été souligné; la victime gardait des séquelles physiques visibles et durables de l'attaque au couteau; la situation personnelle précaire de l'intéressé, qu'il ne devait qu'à lui-même compte tenu de son mépris de la législation en matière de droit des étrangers, n'expliquait en rien ses fréquentations et sa violence gratuite; sa stabilité affective et ses futures responsabilités de père auraient dû l'inciter à adopter un comportement différent; sa collaboration à la procédure avait été mauvaise: il avait accumulé des déclarations invraisemblables; sa prise de conscience était nulle; il n'éprouvait aucune empathie pour la victime et usait sans sourciller du terme "bagarre" pour évoquer ce qui représentait en vérité une mise à mort programmée.
Il ressort de ce qui précède que le recourant a commis une infraction extrêmement grave, dirigée contre le bien juridique le plus important, à savoir la vie et l'intégrité corporelle d'une personne; or, le Tribunal fédéral se montre particulièrement rigoureux en présence d'actes de violence criminelle qui ont gravement porté atteinte à l'intégrité corporelle d'autrui (cf. <ref-ruling> consid. 3.3). Au demeurant, l'assassinat, y compris sa tentative, est une infraction pour laquelle le constituant a entendu se montrer intransigeant (cf. art. 121 al. 3 let. a Cst.). Par la suite, en 2017, l'intéressé a fait l'objet de deux condamnations supplémentaires, à savoir, une amende de 400 fr. pour conduite d'un véhicule en étant titulaire d'un permis de conduire étranger et consommation de stupéfiants, ainsi qu'une peine pécuniaire de 120 jours-amende à 30 fr. pour dénonciation calomnieuse à l'égard d'un gardien de prison. L'intérêt public à l'éloignement du recourant est ainsi manifeste. Dans ces circonstances, seuls des éléments exceptionnels permettraient de faire prévaloir l'intérêt privé de l'intéressé à séjourner en Suisse sur l'intérêt public à l'en éloigner.
2.4. Sous l'angle de cet intérêt privé, si le recourant séjourne dans notre pays depuis 2008, il faut retenir qu'il y est arrivé illégalement et qu'il a été incarcéré pendant quatre ans. Or, les années passées en Suisse dans l'illégalité ne revêtent que peu de poids et celles passées en prison ne sont pas prises en considération (<ref-ruling> consid. 4.3; <ref-ruling> consid. 4.3). Partant, les treize années que le recourant a passé en Suisse ne sont pas déterminantes, sa présence en Suisse n'étant que tolérée, même si l'on peut déplorer les sept ans qui ont été nécessaires à l'Office cantonal de la population pour statuer sur le demande d'autorisation de séjour déposée en 2012. En ce qui concerne le temps écoulé depuis la condamnation de l'intéressé, il doit également être relativisé, dans la mesure où celui-ci a passé une partie importante de cette période, c'est-à-dire du 18 janvier 2013 au 10 février 2017, à exécuter la peine prononcée à son encontre.
Le recourant souligne les circonstances qui entouraient la tentative d'assassinat, à savoir son statut de sans papier nécessitant la protection d'un groupe qui lui assurait un logement et des moyens de subsistance. Si l'on peut comprendre la situation difficile d'une personne dépourvue de titre de séjour, elle ne saurait justifier en aucune manière un tel acte. De plus, non seulement l'intéressé ne devait sa situation précaire qu'à lui-même, puisqu'il était entré en Suisse illégalement, mais en plus il formait déjà un couple avec sa compagne actuelle et celle-ci était enceinte, lorsque l'intéressé s'est rendu coupable de tentative d'assassinat. Certes, le recourant semble avoir changé d'attitude: il fait du bénévolat, a entrepris des démarches afin de favoriser sa réinsertion professionnelle, a obtenu un diplôme de conducteur d'élévateur et des emplois de courte durée; sa situation économique n'en demeure pas moins instable, bien qu'il n'ait jamais émargé à l'aide sociale.
En définitive, l'intérêt du recourant à obtenir un titre de séjour, afin de pouvoir demeurer en Suisse réside essentiellement dans la relation familiale qu'il entretient avec sa compagne et ses enfants. Sous cet angle, un départ de Suisse de l'intéressé entraînera une séparation de la famille, pour le cas où ceux-ci ne le suivraient pas en Algérie. S'agissant de l'intérêt des enfants à vivre avec leurs deux parents, on constatera que les deux premiers enfants du recourant, nés en octobre 2011 respectivement en août 2013, ont grandi de janvier 2013 à février 2017 sans leur père, ce dernier ayant été incarcéré lorsque l'aînée avait un peu plus d'un an, alors que le second est né durant sa détention. Il apparaît néanmoins que l'intéressé s'occupe d'eux depuis sa sortie de prison et qu'ils ont noué une relation intense, selon les termes de la Cour de justice. Sous cet angle, le renvoi de celui-ci dans son pays d'origine aura une influence conséquente sur la qualité du lien qu'il pourrait entretenir avec ses enfants. On relèvera toutefois à ce propos que les concubins ont formé un couple, alors que le recourant séjournait illégalement en Suisse et donc sans garantie de pouvoir y rester. De plus, leur second enfant a été conçu après que l'état civil, en date du 22 octobre 2012, eut déclaré irrecevable une demande formée en vue de mariage. Dans ces circonstances, on doit admettre que la compagne ne pouvait ignorer qu'elle risquait de devoir vivre sa vie de famille à distance ou en partant en Algérie avec son concubin, pays dont elle est originaire. Si elle décide de ne pas le suivre dans ce pays et de rester en Suisse, celui-ci pourra maintenir des contacts réguliers avec ses enfants, compte tenu de la distance raisonnable avec l'Algérie et des moyens de communication actuels. On relèvera enfin que l'intéressé a perpétré les actes qui lui ont été reprochés alors que sa compagne était enceinte, faisant ainsi passer l'intérêt de sa famille au second plan, ce qui ne peut être ignoré dans la pesée des intérêts.
2.5. Certes, la réintégration en Algérie, pays qui subit une crise économique comme le souligne le recourant, ne sera pas facile. L'intéressé a toutefois grandi dans ce pays, puisqu'il l'a quitté en 2008 alors qu'il était âgé de 24 ans, il en parle la langue et il y a obtenu un diplôme de mécanicien et un permis de conduire poids-lourds. De plus, il y retrouvera sa mère et une de ses deux soeurs.
2.6. En conclusion, on ne discerne pas de circonstances exceptionnelles propres à contrebalancer le passé pénal du recourant, dont l'extrême gravité ne saurait être niée, et qui seules auraient permis, conformément à la jurisprudence, de faire primer son intérêt privé à demeurer en Suisse sur l'intérêt public à l'en éloigner, de sorte à justifier de lui octroyer un titre de séjour.
3.
Les considérants qui précèdent conduisent au rejet du recours.
Succombant, le recourant doit supporter les frais judiciaires (art. 66 al. 1 LTF). Il n'y a pas lieu d'allouer de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué à la représentante du recourant, à l'Office cantonal de la population et des migrations et à la Cour de justice de la République et canton de Genève, Chambre administrative, 2ème section, ainsi qu'au Secrétariat d'Etat aux migrations.
Lausanne, le 11 février 2021
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
La Greffière : Jolidon